boj 1168 - 요세푸스 문제 2

목차

개요

설명

코드

 

---

개요

이 문제는 k 번째 원소를 효율적으로 찾는 문제입니다. 이는 segment tree를 사용하여 구할 수 있습니다. 이 문제는 [boj 12899-데이터 구조]와 굉장히 유사하므로 이를 참고하시면 됩니다.

 

k 번째 원소를 segment tree를 이용해 효율적으로 찾는 방법은 [boj 12899-데이터 구조]를 참고하세요.

 

이 포스트에서는 k를 어떻게 계산해야 할 지에 대해서만 다루겠습니다.

---

설명

요세푸스 문제는 수열에서 일정한 간격으로 점프해 가면서 숫자들을 하나씩 빼낸 수열입니다.

 

백준의 예제 N = 7, K = 3의 경우에는 아래 그림을 보면 이해 하실 수 있으리라 생각합니다.

 

원소를 지우고 나면, 그 원소부터 다시 k개 만큼 뒤로 이동한 뒤에 또 그 원소를 지웁니다. 만약, 이 과정에서 배열의 끝에 도달한다면, 처음으로 다시 되돌아갑니다. (원 형태로 이어져있다고 생각하면 편합니다.)

 

이 문제는 segment tree에서 k번째의 원소를 찾는 문제와 거진 동일합니다. 다만, 몇 번째 원소를 찾을 것이냐를 잘 계산해줘야 합니다.

 

몇 번째 원소를 찾을지를 rank라 할 때, 이는 다음과 같이 계산할 수 있겠지요. 현재 원소는 제외되었으니 우리가 찾아야 할 다음 원소의 순위는 1단계 낮아졌을 것입니다. 따라서 -1을 해줘야 합니다.

 

$$rank = rank + k - 1$$

 

그러나, 배열 끝을 넘어가면 다시 처음위치로 돌아가서 남은 만큼을 다시 이동해야 합니다. 이는 나머지 연산을 통해서 계산할 수 있습니다.

 

$$rank = (rank + k - 2)\ \%\ size + 1$$

 

여기서 size는 현재 남은 원소의 수입니다.

 

그런데 식이 조금 복잡해졌습니다.

왜 -2일까요? 다시 말해, 원래 계산식에서 왜 -1이 더 추가되었을까요? 이는 모듈러 연산 (0 ~ size-1)과 우리의 순위 (1 ~ size) 사이에서 1씩 차이가 있는걸 보정해주기 위함입니다.

 

모듈러 연산은 불가피 한데, 값은 0 ~ size-1이 나오게 되니, 모듈러 연산을 위해 먼저 -1을 빼고 계산한 뒤에 다시 보정해주는 방식입니다.

 

자세한 과정은 아래 그림으로 첨부했습니다.

---

코드

※주의할 점

1. k 번째 원소를 구하기 위한 과정에서 k값을 잘 계산해야 합니다.
2. Segment tree는 처음에 모든 원소를 1개가 있다는 가정으로 초기화 해야합니다. 이 후, k 번째 원소를 찾을 때 마다, 출력하고 값을 제거하면 됩니다.

#include<stdio.h>
#define IMAX 2000000
using namespace std;

int arr[100000];
class Tree{
        int node[1<<18];

        public:
        int Init(int cur, int left, int right){
                if(left==right){
                        return node[cur] = arr[left];
                }
                int mid = (left+right)/2;
                return node[cur] = Init(cur*2, left, mid) + Init(cur*2+1, mid+1, right);
        }

        int Delete(int cur, int left, int right, int rank){
                if(left==right){
                        node[cur] -= 1;
                        return left;
                }
                int mid = (left+right)/2;
                int ret = 0;
                if(rank <= node[cur*2]) ret = Delete(cur*2, left, mid, rank);
                else ret = Delete(cur*2+1, mid+1, right, rank-node[cur*2]);
                node[cur] = node[cur*2] + node[cur*2+1];
                return ret;
        }
};
int main(){
        int N, K;
        scanf("%d %d",&N, &K);

        for(int i=0;i<N;i++){
                arr[i] = 1;
        }
        Tree *t = new Tree();
        t->Init(1, 0, N-1);

        int rank = K;

        printf("<");
        for(int i=0;i<N;i++){
                printf("%d",t->Delete(1, 0, N-1, rank)+1);

                if(i<N-1){
                        rank = (rank+K-2)%(N-i-1)+1;
                        printf(", ");
                }
        }
        printf(">");
}