BOJ 1168 요세푸스 문제 2

1 개요

BOJ 1168 요세푸스 문제 2

• 백준 온라인 저지 1168번 문제
• BOJ 45단계

2 C++

#include <bits/stdc++.h>
using namespace std;

int N, K;
vector<int> segTree;

// 세그먼트 트리 초기화
void init(int node, int start, int end) {
    if (start == end) {
        segTree[node] = 1;
        return;
    }
    int mid = (start + end) / 2;
    init(node * 2, start, mid);
    init(node * 2 + 1, mid + 1, end);
    segTree[node] = segTree[node * 2] + segTree[node * 2 + 1];
}

// K번째 사람을 찾아 제거
int query(int node, int start, int end, int k) {
    if (start == end) return start;
    int mid = (start + end) / 2;
    if (k <= segTree[node * 2]) {
        return query(node * 2, start, mid, k);
    } else {
        return query(node * 2 + 1, mid + 1, end, k - segTree[node * 2]);
    }
}

// 사람 제거 업데이트
void update(int node, int start, int end, int index) {
    if (index < start || index > end) return;
    if (start == end) {
        segTree[node] = 0;
        return;
    }
    int mid = (start + end) / 2;
    update(node * 2, start, mid, index);
    update(node * 2 + 1, mid + 1, end, index);
    segTree[node] = segTree[node * 2] + segTree[node * 2 + 1];
}

int main() {
    cin >> N >> K;
    segTree.resize(N * 4);
    init(1, 1, N);

    int current = K;
    cout << '<';
    for (int i = 0; i < N; ++i) {
        int person = query(1, 1, N, current);
        cout << person;
        if (i < N - 1) cout << ", ";
        update(1, 1, N, person);

        if (N - i - 1 > 0) current = (current + K - 1) % (N - i - 1);
        if (current == 0) current = N - i - 1;
    }
    cout << '>';
}