백준[1168] 요세푸스 문제 2

요세푸스 문제 2

문제 링크

http://icpc.me/1168

1168번: 요세푸스 문제 2

풀이

이 문제를 응용하여 풀 수 있는 문제다.

x = k라 할 때 처음엔 x번째 수를 제거하고 그다음은, x + k-1번째 수를 제거하고 다음은 x + 2*(k-1) 번째를 제거는 과정을 계속해서 반복한다. 이때 x + i(k - 1)이 남은 수의 개수보다 크다면 x + i(k-1) % (남은 수의 개수)를 취한다. 하지만 그 값이 0이 되면 안 되기 때문에 남은 수의 개수로 나누어 떨어질 때는 x = (남은 수의 개수)로 만든다.

cf) 나는 출력 형식을 제대로 보지 않아서 시간을 약간 날렸다. 출력 형식을 잘 확인하자.

코드

#include <cstdio>

int tree[400005];

int init(int node, int s, int e) {
    if (s == e) return tree[node] = 1;
    int mid = (s + e) >> 1;
    return tree[node] = init(2 * node, s, mid) + init(2 * node + 1, mid + 1, e);
}

int query(int node, int s, int e, int k) {
    tree[node]--;
    if (s == e) return s;
    int mid = (s + e) >> 1;
    if (tree[2 * node] >= k) return query(2 * node, s, mid, k);
    else return query(2 * node + 1, mid + 1, e, k - tree[2 * node]);
}

int main() {
    int n, k; scanf("%d %d", &n, &k);
    init(1, 1, n);
    int x = k;
    printf("<");
    for (int i = 0; i < n - 1; i++) {
        printf("%d, ", query(1, 1, n, x));
        x += k - 1;
        if (x % tree[1] == 0) x = tree[1];
        else x %= tree[1]; 
    }
    printf("%d", query(1, 1, n, x));
    printf(">");
}