문제 : https://www.acmicpc.net/problem/1168
1168번: 요세푸스 문제 2
첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 100,000)
www.acmicpc.net
문제 파악하기
요세푸스 수열을 빠르게 구하는 문제입니다. 이전 문제(요세푸스 문제)와 다른 점은 N의 크기가 100,000으로 늘어났으며, 시간 제한도 0.15초로 줄어들었습니다. 그래서 이전 문제에서 사용한 알고리즘인 큐(배열)을 활용한 전탐색(브루트포스) 알고리즘으로는 해결할 수 없습니다. 문제를 해결하기 위해서는 다음 숫자를 좀 더 빠르게 찾아야하며, 여기서 자료구조를 활용하면 문제를 해결할 수 있습니다.
문제 해결하기
문제를 해결하기 위해서는 순열의 다음 숫자를 빠르게 찾아야 하며, 이 과정에서 특별한 자료구조를 사용할 수 있습니다. 그렇다면 어떤 자료 구조를 사용해야 할까요? 문제를 단순하게 생각하면 현재 숫자(idx)에서 K번째 위치에 있는 숫자를 찾아야 합니다. 이런 경우에 활용할 수 있는 자료구조는 바로 세그먼트 트리입니다. 세그먼트 트리는 루트부터 시작해서 왼쪽과 오른쪽 자식의 값을 참고하여 K번째 숫자를 O(logN)만에 찾을 수 있습니다.
그렇다면 현재 숫자(idx)에서 K번째 숫자를 어떻게 찾을 수 있을까요? 이 경우에는 현재 숫자부터 K번째 숫자는 현재 숫자보다 왼쪽에 위치한 숫자들의 개수를 활용하면 찾을 수 있습니다. 만약 현재 위치(idx)보다 왼쪽에 위치한 숫자들의 합이 lt라면 (lt + K)번째 숫자가 바로 K번째 숫자를 의미하기 때문입니다. 따라서, 2번의 탐색(왼쪽 숫자의 개수 + K번째 숫자 위치)을 거치면 다음 숫자를 찾을 수 있습니다.
단, 여기서 문제가 되는 경우는 총 2가지 입니다. 첫 번째, 오른쪽에 K개의 숫자가 남아있지 않은 경우입니다. 이 경우에는 오른쪽에 남아있는 숫자의 개수를 제외한 다음에 왼쪽부터 다음 숫자를 찾으면 됩니다. 예를 들어, N과 K가 7과 3이며, 현재 { 3, 6 }까지 찾고 다음 숫자를 찾는 경우라고 가정해보겠습니다. 이 경우, 다음 숫자는 6보다 오른쪽에 위치할 수 없습니다. 따라서, 이 경우에는 왼쪽에서 2번째 숫자를 찾아야 합니다.
두 번째, K가 남아있는 사람 수(p)보다 커지는 경우입니다. 이 경우에는 숫자를 적절하게 줄여줄 수 있습니다. 왜냐하면 K가 아무리 크더라도 결국 선택되는 다음 숫자는 현재 남아있는 사람 중에서 선택되기 때문입니다. 예를 들어 현재 3명의 사람이 남아있다고 가정해봅시다. 여기서 첫 번째 사람이 선택되는 K의 경우는 여러 가지 나올 수 있습니다. K=1인 경우도 포함되며, K=4, K=7, ... 등등 수많은 경우가 첫 번째 사람이 선택됩니다. 따라서, 쉬운 계산을 위해서는 K의 값을 P의 값(사람 수)보다 작게 변경할 수 있으며, 변경할 때에는 K%P의 값에 따라 변경할 수 있습니다.
이렇게 2가지 경우를 조심하면 문제를 해결할 수 있습니다. 문제를 해결하는 소스코드는 다음과 같습니다.
소스코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
|
#import <stdio.h>
#import <vector>
#define NMAX 100010
using namespace std;
int N, K, mv;
vector< int > ans;
int sz, idx, rt, pos;
int segTree[NMAX*4];
int getCnt(int l, int r) {
int ret = 0;
while(l<=r) {
if(l%2==1) ret += segTree[l++];
if(r%2==0) ret += segTree[r--];
l/=2; r/=2;
}
return ret;
}
int search(int idx, int val) {
while(idx < sz) {
if(val <= segTree[idx*2]) idx = idx*2;
else {
val -= segTree[idx*2];
idx = idx*2+1;
}
}
return idx-sz;
}
int main() {
// 입력
scanf("%d %d", &N, &K);
// 사람 수를 체크하는 세그먼트 트리 생성
for(sz=1;sz<N;sz<<=1);
for(int idx=sz+N-1;idx>0;idx--) {
if(idx >= sz) segTree[idx] = 1;
else segTree[idx] = segTree[idx*2] + segTree[idx*2+1];
}
// 요세푸스 순열 구하기
idx = 0;
for(int i=N;i>0;i--) {
// 이동 횟수
if(i>=K) mv = K;
else {
if(K%i == 0) mv = i;
else mv = K%i;
}
// 오른쪽에 남은 사람 수
rt = getCnt(sz+idx, sz+N-1);
// 다음 사람 찾기
// mv <= rt: 오른쪽에 남은 사람 중 한명이 다음 사람 >> (i-rt) + mv번째 사람 찾기
// mv > rt: 왼쪽에 남은 사람 중 한명이 다음 사람 >> mv-rt번째 사람 찾기
if( mv <= rt ) pos = search(1, (i-rt)+mv);
else pos = search(1, mv-rt);
// 현재 사람 저장하기
ans.push_back(pos+1);
// 갱신하기
pos += sz;
while(pos>0) {
segTree[pos]--;
pos /= 2;
}
// 다음에 시작할 사람 찾기
if( mv <= rt-1 ) idx = search(1, (i-rt)+mv);
else idx = search(1, mv-rt);
}
// 출력
printf("<");
for(int i=0;i<N-1;i++) printf("%d, ", ans[i]);
printf("%d>", ans[N-1]);
}
|
cs |
후기
세그먼트 트리를 명확하게 이해한 경우에 풀 수 있는 문제라고 생각합니다. 세그먼트 트리의 응용 버전인 동적 세그먼트 트리나 퍼시스턴트 세그먼트 트리와 같은 고급 자료구조를 활용하기 위한 세그먼트 트리 응용 문제로, 세그먼트 트리를 연습하는 사람에게 추천하고 싶은 문제입니다.