알고스팟 JOSEPHUS 풀이

요즘 공부하고 있는 <알고리즘 문제 해결전략>이라는 책에 나오는

조세푸스 문제를 풀어보았다.

책에서는 연결 리스트로(구현은 c++ STL list) 구현했는데

풀이를 보기 전에 나는 큐로 문제를 해결해 보았다.

출처-알고스팟(문제 ID : JOSEPHUS)

링크 : https://algospot.com/judge/problem/read/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

노트

첫 번째 예제에서는 1번, 4번, 2번, 6번이 순서대로 죽고 3번과 5번만이 남습니다.

해결방법은 간단하다. 리스트 또는 큐에서 첫번째 병사를 죽인 후 (해당 원소를 제거) K번째 병사에 해당하는 원소로 이동해서 삭제하고 그것을 두 원소(두명의 병사)만 남을때까지 계속 반복하면 되는것이다.

큐로 구현한 내 문제풀이에서는 k번째 병사에 해당하는 원소가 큐의 맨앞에 나오도록 k-1번 디큐와 인큐를 반복하고 k번째 병사를 제거한 두명의 병사가 남을때까지 반복했다.

이 문제해결방법(또는 리스트로 구현한 방법)의 시간복잡도는 O(N*K)다. 동적 계획법이나 기타 다른방법으로 최적화가 가능하다고 책에서 설명하고 있는데 나중에 한번 구현해 보아야겠다.

아래는 c++로 구현한 소스코드이다.

알고스팟에서 통과된 코드이니 문제는 없을듯 싶다.

#include <iostream>
#include <queue>
using namespace std;

//조세푸스 문제를 해결하는 함수
void josephus(int N, int K)
{
	queue<int> survivors; //생존자 큐
	
	for (int i = 1;i <= N;i++) //각 병사들에게 번호 할당
	{
		survivors.push(i); //큐에 enqueue
	}

	survivors.pop();//첫번째 병사 자살

	int nextperson; //다음에 자살한 병사 


	while (survivors.size() > 2) //마지막 두명이 남을때까지 반복
	{
		//k번째 병사를 고르는 반복문
		for (int i = 0;i < K-1;i++)
		{
			nextperson = survivors.front();//다음 병사를 선택
			
			 //자살할 병사가 아니므로 디큐후 다시 인큐
			survivors.pop();
			survivors.push(nextperson);
		}
		//큐의 맨앞에 있는 병사가 k번째 병사이므로 자살(디큐)
		survivors.pop();
		
	}
	//while문이 끝나면 큐에는 단 두명의 병사만 남는다
	//큐가 오름차순으로 유지되지 않으므로 남은 병사들의 번호를 오름차순으로 출력
	if(survivors.front()>survivors.back())
	cout << survivors.back() << " " << survivors.front() << endl;
	else
	cout << survivors.front() << " " << survivors.back() << endl;

}
int main()
{
	int c, N, K;
	cin >> c;
	for (int i = 0;i < c;i++)
	{
		
		cin >> N >> K;
		josephus(N, K);
	}
	
	return 0;
}

실행결과 : 빨간상자의 숫자가 출력결과