18.5 조세푸스 문제

n명의 사람이 있고, 첫 번째 사람을 기준으로 k번째 사람이 차례로 죽어나갑니다.

이 때 2명이 되면 2명은 살아남습니다. 

조세푸스가 2명 안에 들기 위해 몇 번 째에 있어야 하는지 구하는 문제입니다.

(첫번 째 사람 1번, 시계 방향으로 번호 증가)

 

C++의 list를 이용하여 구현하였습니다.

list의 iterator를 kill이라 하고 처음에 kill = list.begin( ) 으로 잡습니다.

이후 2명이 남을 때까지 kill의 위치의 노드를 지우고 (erase) 노드를 한 칸씩 당기는 것을 반복합니다.

 

코드

#include<iostream>
#include<vector>
#include<list>

using namespace std;

int C, N, K;

void josephus(int n, int k) {
	list<int>survivors;
	for (int i = 1; i <= n; i++)
		survivors.push_back(i);

	list<int>::iterator kill;
	kill = survivors.begin();

	while (n > 2) {
		kill = survivors.erase(kill);
		if (kill == survivors.end())
			kill = survivors.begin();
		n--;
		for (int i = 0; i < k - 1; i++) {
			kill++;
			if (kill == survivors.end())
				kill = survivors.begin();
		}
	}
	cout << survivors.front() << ' ' << survivors.back() << '\n';
}

int main()
{
	cin >> C;
	cout << "\n===========\n";
	while (C--) {
		cin >> N >> K;
		josephus(N, K);
		cout << "\n===========\n";
	}
}

결과