BOJ 1168 : 요세푸스 문제 2

알고리즘 문제 전체 링크

 

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

 

참고

- BOJ 11866, 1158 : 요세푸스 문제 0, 요세푸스 문제

- 구간 합 구하기 with 바텀 업 세그먼트 트리 (Bottom-Up Segment Tree)

- BOJ 1655 : 가운데를 말해요 with 우선순위 큐

 

 

큐(Queue)를 사용하는 BOJ 11866, 1158 : 요세푸스 문제 0, 요세푸스 문제보다 N이 매우 큰 경우다.

세그먼트 트리에서 n번째 값을 찾는 방식으로 문제를 해결할 수 있다.

---

N이 100,000이고, 100,000보다 2배 이상 큰 2의 배수는 262,144이다.

따라서 tree의 사이즈는 다음과 같다.

int tree[262144];

 

이제 N보다 큰 2의 배수를 구해보자.

for (leafSize = 1; leafSize <= N; leafSize <<= 1);

 

tree에 저장할 배열의 시작 index는 leafSize에서 1을 빼면 된다.

start = leafSize - 1;

 

BOJ 1655 : 가운데를 말해요 with 세그먼트 트리에서

세그먼트 tree를 업데이트 하는 함수와 배열에서 index를 구하는 함수는 다음과 같다.

가운데를 말해요에서는 가운데번째 index만 찾았지만, 여기서는 주어진 index를 찾으면 된다.

void update(int index, int diff)
{
	index += start;

	while (index > 1)
	{
		tree[index] += diff;
		index /= 2;
	}
}

int getNumber(int index)
{
	int treeIdx = 1;
	while (treeIdx < leafSize)
	{
		if (index <= tree[treeIdx * 2]) treeIdx *= 2;
		else
		{
			index -= tree[treeIdx * 2];
			treeIdx = treeIdx * 2 + 1;
		}
	}

	return treeIdx - start;
}

 

처음에 구해야할 index = K이고, 남아있는 수는 N이다.

위의 예시대로면 7개의 수에서 3번째 수를 구하고 답은 당연히 3이다.

index = K, remain = N;

 

getNumber로 숫자를 구했다면, 이 숫자를 지우기 위해 update에 -1을 넣어 갱신한다.

그리고 현재 index는 제거된 숫자에 의해 1이 감소하고 K만큼 증가하게 된다.

또한 전체 남은 수도 1이 감소해야 한다.

index가 remain보다 클 수 있기 때문에 나머지 연산을 이용하여 index를 맞춘다.

나머지 연산으로 index가 1 ~ N 사이가 되도록 1을 뺀 후, 다시 1을 더하도록 한다.

for (int i = 1; i <= N - 1; i++)
{
	int number = getNumber(index);

	printf("%d, ", number);
		
	update(number, -1);

	index = index - 1 + K;
	remain = remain - 1;
	index = (index - 1) % remain + 1;
}

 

마지막 출력은 ,가 없기 때문에 위의 과정을 N - 1번 반복하고 마지막 1회는 따로 호출한다.

printf("%d>\n", getNumber(1));

 

전체 코드는 다음과 같다.

#include <stdio.h>

int N, K;
int tree[262144]; 
int start, leafSize;

void update(int index, int diff)
{
	index += start;

	while (index > 1)
	{
		tree[index] += diff;
		index /= 2;
	}
}

int getNumber(int index)
{
	int treeIdx = 1;
	while (treeIdx < leafSize)
	{
		if (index <= tree[treeIdx * 2]) treeIdx *= 2;
		else
		{
			index -= tree[treeIdx * 2];
			treeIdx = treeIdx * 2 + 1;
		}
	}

	return treeIdx - start;
}

int main()
{
	scanf("%d %d", &N, &K);

	for (leafSize = 1; leafSize <= N; leafSize <<= 1);

	start = leafSize - 1;
	
	for (int i = 1; i <= N; i++) update(i, 1);
	
	int index, remain;

	index = K, remain = N;
	
	printf("<");
	for (int i = 1; i <= N - 1; i++)
	{
		int number = getNumber(index);

		printf("%d, ", number);
		
		update(number, -1);

		index = index - 1 + K;
		remain = remain - 1;
		index = (index - 1) % remain + 1;
	}

	printf("%d>\n", getNumber(1));
	
	return 0;
}