18.5 문제: 조세푸스 문제(문제ID: JOSEPHUS)

문제
1세기에 살던 역사학자 조세푸스는 로마와의 전쟁에서 패해 N - 1명의 동료 병사들과 함께 출구가 없는 동굴에 포위당했다고 합니다. 동료 병사들은 로마에 항복하느니 차라리 자살하자고 결의했고, 포위당한 N명의 사람들이 모두 원형으로 둘러선 뒤 순서대로 자살하기로 했습니다. 한 사람이 자살하면, 다음에는 그 사람으로부터 시계 방향으로 K번째 살아 있는 사람이 자살하는 것입니다.

조세푸스의 책에 따르면 조세푸스와 다른 병사 하나만이 살아남았을 때 이들은 마음을 바꿔 로마에 항복해서 살아남았다고 합니다. 마지막 두 명 중 하나가 되기 위해서는 조세푸스는 첫 번째 병사로부터 몇 자리 떨어진 곳에 있어야 했을까요?

입력
입력의 첫 번째 줄에는 테스트 케이스의 개수 C (C≤50)가 주어집니다. 각 테스트 케이스는 두 개의 정수 N, K로 주어집니다(3≤N≤1000, 1≤K≤1000).

출력
각 테스트 케이스에 두 개의 정수로, 마지막 살아남는 두 사람의 번호를 오름차순으로 출력합니다. 첫 번째로 자살하는 병사의 번호가 1이며, 다른 사람들의 번호는 첫 번째 병사에서부터 시계 방향으로 정해집니다.

예제 입력
2
6 3
40 3

예제 출력
3 5
11 26

🤔생각

이전에 백준에서 요세푸스 문제를 c언어로 풀어본 경험이 있다. 그래서 원순열을 생각하며 2명이 남을 때 까지 누가 죽을것인지를 선택하고 리스트에서 제거해주면 될거라 생각하였다.

😯부족했던 부분

코드를 제출했었을 때 시간초과가 났었는데 그 이유는 리스트의 크기를 구할 때 std::list::size()를 사용했기 때문이다. std::list::size()는 vector의 size와 string의 size와는 다르게 O(n)(C++11에서는 상수시간인거 같다)의 시간복잡도를 가진다고 한다.

😀코드

#include<iostream>
#include<list>

using namespace std;

int N, K;
list<int> lt;

void ans() {
	list<int>:: iterator iter = lt.begin();

	iter = lt.erase(iter);
	N--;
	while (N > 2) {
		for (int i = 0; i < (K - 1) % N; i++) {
			if (iter == lt.end())
				iter = lt.begin();
			iter++;
		}
		if (iter == lt.end())
			iter = lt.begin();

		iter = lt.erase(iter);
		N--;
	}
}

int main(void) {
	int C;

	cin >> C;
	for (int i = 0; i < C; i++) {
		cin >> N >> K;

		lt.clear();

		for (int j = 0; j < N; j++)
			lt.push_back(j + 1);

		ans();

		list<int> ::iterator iter = lt.begin();
		cout << *iter++;
		cout << " " << *iter << "\n";
	}
	return 0;
}

👏후기

문제를 풀다보면 종종 STL을 사용하는데 내가 사용하는 메서드의 시간 복잡도에 대해서 잘 알아야 될 필요성을 느꼈다.