조세퍼스 문제 시리즈 (백준 1158, 1168, 11025, 1179)

조세퍼스 문제 시리즈를 풀어보았다.

조세퍼스 문제는 꽤 유명한 문제인데, 사람 n명이 원탁에 순서대로 둥글게 둘러앉은 뒤, 처음에 k번째 사람이 집에 가고, 그 다음에 집에 간 사람의 위치를 기준으로 하여 k번째 사람을 제거하고.. 를 반복하는 문제이다.

7명일 때 k가 3이면 다음과 같다.

1 2 3 4 5 6 7 => 3

1 2 4 5 6 7 => 6

1 2 4 5 7 => 2

1 4 5 7 => 7

1 4 5=> 5

1 4 => 1

4 => 4

백준 1158번: 조세퍼스 문제

정직한 구현 문제. 보통 큐를 이용하는데, 처음에 숫자를 순서대로 넣고 k - 1번 큐에서 빼고 집어넣은 뒤, 마지막 k번째 사람은 집어넣지 않고 출력한다.

대략 큐를 처음 써보는 사람들을 위한 문제 정도다.

백준 1168번: 조세퍼스 문제 2

n과 k가 10만이 되어서 $O(nk)$인 정직한 구현으로는 풀기 힘들다.

조세퍼스 문제의 핵심은 앞에서 i번째인 사람을 빨리 찾을 수 있어야 하고, 사람의 제거가 빨라야 한다.

아쉽게도 이 둘을 동시에 만족하는 자료구조는 그리 흔하지 않다.

일단 상식적인 범위 내에서는, 펜윅 트리와 binary search를 통해 문제를 해결할 수 있다.

모든 사람을 존재하면 1, 없으면 0으로 두면, 앞에서부터 i번째 사람의 번호는 binary search를 통해 1~j-1번까지의 합이 i-1, 1~j번까지의 합이 i인 인덱스 j를 찾음으로써 찾을 수 있다. 시간 복잡도는 대략 $O(n\log^2{n})$ 정도이다.

앞에서 말한 인덱스를 통한 접근과, 추가/제거를 빠르게 해주는 자료구조를 이용하는 방법도 있다. 잘 알려져 있지는 않은데, 다음과 같이 사용 가능하다.

#include <iostream>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;

int main() {
	tree<int, null_type, std::less<int>, rb_tree_tag, tree_order_statistics_node_update> s;

	s.insert(1);
	s.insert(2);
	s.insert(5);
	s.insert(7);
	std::cout << *s.find_by_order(1) << std::endl; // s[1] = 2
	s.erase(2);
	std::cout << *s.find_by_order(1) << std::endl; // s[1] = 5
}

190917 내용추가)

이 문제를 vector와 erase를 이용해 의외로 쉽게 풀어낼 수 있다.

복잡도는 $O(n^2)$이 맞지만, vector의 erase는 memmove를 이용하기 때문에 겁나 빠른 $O(n^2)$이 되어서 문제를 풀 수 있다.

백준 11025번: 조세퍼스 문제 3

이제 n과 k가 500만 수준이다. 앞에서 사용한 방법도 이제는 사용을 못한다. (이때부터는 대략 수학문제가 된다)

이제부터는 매번 집에 가는 사람들을 다 구할 필요는 없고, 마지막에 집에 가는 사람이 누구인지만 구해내면 된다.

이 문제를 다행히도 O(n)에 풀어낼 수 있는데 다음과 같은 점화식이 성립한다.

$j(n, k) = (j(n - 1, k) + k) mod n$, $j(1, k) = 0$

$j(n, k)$는 마지막에 집에 가는 사람의 번호이다. 이때 백준 문제에서는 1-indexed지만 점화식은 0-indexed로 해야한다는 것에 유의하자. 출처는 위키피디아.

위 점화식은 아주 자명한데, 집에 가는 사람이 정해지면 그 사람으로부터 다음 집에 가는 사람의 위치를 구한 뒤, 인덱스를 보정해주는 작업만 진행한 것이다.

백준 1179번: 마지막 조세퍼스 문제

마지막 문제이다. 이제 n이 $O(n)$으로도 안 풀릴 만큼 크고, 대신 k는 작다.

이 때 사용할 수 있는 공식 또한 위키피디아에 나와있다.

공식이 약간 잘못된 감이 있는데, k = 1이면 n'가 0이 되므로 mod n'을 계산할 수가 없다. k = 1이면 g(n, k) = n - 1도 명시를 해야 할 것 같다.

아무튼, 이번에는 이 공식에 맞추어 잘 계산해주면 된다. 공식이 꽤 복잡해서 왜 저런 공식이 성립하는지 알기 힘들다. 차근차근 해석해보자.

기본적인 방법은 조세퍼스 문제 3을 푸는 것과 유사한데, 대신 한번에 많은 후보들을 제외시키는 것이 핵심이다.

가령 1, 2, 3, ..., n번 사람이 테이블에 앉아 있을 때 k = 3이라면 테이블을 한 바퀴 돌기 전까지는 순서대로 3, 6, 9, ...번 사람들이 집에 가게 된다. 다시 말해 k의 배수번째 사람들이 모두 제거되는 것이다.

따라서 사람이 제거된 후 남은 사람이 n'이 되고, n'번째에 새로운 기준점 2가 생기게된다.

이제 이 기준점을 기준으로 $g(n', k)$를 구한다면, 이 사람은 기준점 1을 기준으로 본다면 $g(n', k) - (n \mod k)$번에 위치하게 된다. 음수면 n'를 더해주어야 하는데, 이를 위키피디아에서는 그냥 mod n'로 표기한 듯 하다.

이제 제거된 사람들을 뺀 상태에서 구한 이 값을 제거된 사람을 사람들을 제거하기 전 인덱스로 보정해주어야 하는데, 이를 해주는 것이 바로 i * k / (k - 1)이다.

곱이 먼저 되고 나누기가 이후에 되어서 약간 직관적으로 감이 오지 않을 수 있는데, 대략 k - 1번마다 2를 더해주고 그 외에는 1을 더해주는 정도로 이해하면 될 것 같다. 예컨대 k = 4라면 다음과 같은 결과가 나온다.

i	k * i	k * i / (k + 1)
0	0	0
1	4	1
2	8	2
3	12	4
4	16	5
5	20	6
6	24	8
7	28	9
8	32	10
9	36	12

코드

1158.cpp

1168.cpp

11025.cpp

1179.cpp