c언어 1168번 요세푸스 문제 2 (백준)

https://www.acmicpc.net/problem/1168

#include <stdio.h>

int tree[400004] = {};

int update(int s, int e, int node, int i, int dif) {
	if(s>i || e<i) return tree[node];
	if(s==e) return tree[node] = dif;
	int m = (s+e)/2;
	return tree[node] = update(s,m,node*2,i,dif) + update(m+1,e,node*2+1,i,dif);
}

int find(int s, int e, int node, int cnt) {
	if(s==e) return s;
	int m = (s+e)/2;
	if(tree[node*2]>=cnt) find(s,m,node*2,cnt);
	else find(m+1,e,node*2+1,cnt-tree[node*2]);
}

int main(void) {
	int n,k,a=0,c=0,d;
	scanf("%d %d",&n,&k);
	c=n;
	a=k;
	for(int i=1; i<=n; i++) update(1,n,1,i,1);
	
	printf("<");
	for(int i=1; i<=n; i++) {
		d = find(1,n,1,a);
		printf("%d",d);
		if(i<n) printf(", ");
		else break;
		update(1,n,1,d,0);
		a+=(k-1);
		--c;
		if(a>c) {
			a %= c;
			if(a==0) a = c;
		} 
	} printf(">");
}

 

풀이 : 세그먼트 트리, 몇번째로 작은 수 인가?

 

반복문으로 구현한다면, 요세푸스 문제의 경우 아직 선택되지 않은것만을 탐색하여 그 횟수가 k가 될 때 숫자를 고르는 형식으로 구현하나 이는 아시다시비 너무나도 많은 시간이 걸립니다. 이것을 세그먼트 트리와 몇번째로 작은 수? 라는 개념으로 접근하면 빠르게 해결 할 수 있습니다.

 

ex) 7 3

답 :

<3, 6, 2, 7, 5, 1, 4>

 

1 2 3 4 5 6 7

 

0. 세그먼트트리로 각 숫자들이 존재하지는 지를 저장합니다. 있다면 1, 없다면 0

 

1. 3번째로 작은 수 ->3

 

2. 그다음 숫자는 6이나, 이것을 1~6중 5번째로 작은 수로 볼 수 있습니다. 여기서 5라고 생각해서는 안됩니다. 왜냐면 3이 더이상 존재하지 않기 때문에 1~6에 있는 수는 1,2,4,5,6 이기 때문입니다. 즉 5번째로 작은 수를 고르면 됩니다.

 

3. 이를 확장하면 1~9 중 7번째로 작은 수를 찾아야 합니다 (7인 이유는 1~9에서 3,6이 제거되었기 때문) 그러나 주어진 숫자는 1~7까지이며 이 범위에 남아 있는 수는 5개 밖에 없습니다. 그렇다면 이것은 아래처럼 생각할 수 있습니다.

1 2 4 5 7 | 1 2 4 5 7 | | 1 2 4 5 7 |  | 1 2 4 5 7 | ... 이렇게 연속적으로 반복한다고 보면

7번째로 작은 수는 2번째로 작은 수로 볼 수 있습니다. 이것은 범위에 남아있는 수로  MOD를 하거나 빼기를 하면 얻어낼 수 있는 값입니다.

 그러므로 1~7에서 2번째 -> 2번째로 작은 수는 (3,6은 제외됬으니) 2번입니다.

 

4. 3.에서 2번째로 작은 수를 구했기 때문에 이번에는 1 2 4 5 7 에서 5번째로 작은, 다시말해 1 4 5 7 에서 4번째로 작은 것을 고릅니다.

 

1~7에서 (3,6,2 제외됨) 4번째로 작은 숫자는

1 4 5 7 |  1 4 5 7 | 1 4 5 7 | 1 4 5 7 | 1 4 5 7 | ... 의 반복으로 보면

4번째로 작은 숫자를 구할 수 있습니다. 이는 7입니다.

 

이를 반복하면 반복문으로 하는 것 보다 더 빨리 값들을 얻어 낼 수 있습니다.

주의할 점은 범위가 넘어가서 MOD를 할 때, 0이 되는 경우가 있습니다. 이것의 경우 실제로는 0이 아니라 MOD를 해주는 값이 되어야 오류가 나지 않습니다.

ex) 범위에 5개, 10번째

10 mod 5 = 0 이 되어버리지만, 실제 값은 5번째 가 되어야 합니다.

 

 

<공식>

1. 세그먼트  트리의 말단노드를 1로 하여 초기화 합니다.

2.0 y개에서 x번째로 작은 수를 구합니다. (y는 제거되지 않은 숫자들의 개수를 의미합니다)

2.1 x의 초기값은 k입니다. y의 초기값은 n입니다.

2.2 작은 수를 찾은 다음 x에 k-1을 더해줍니다 (-1을 하는 이유는 범위에서 숫자 1개가 제거되었기 때문)

2.3 y값은 숫자가 1개 제거되었으니 1 감소 해줍니다. --y;

2.4 만약 x가 y개보다 초과라면 x = x mod y 을 해줍니다 (범위에 들어오도록)

2.5 단 x가 0이 되버리면 x = y 을 해줍니다.

3. 2의 과정을 n번 반복하면 됩니다.

 

<추가 : x번째 값 구하기>

https://h202.tistory.com/739

c언어 2243번 사탕상자 (백준)

참고