[백준] 1158번 - 요세푸스 문제 / C++

문제

요세푸스 문제는 다음과 같다.

1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(≤ N)가 주어진다. 이제 순서대로 K번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다. 원에서 사람들이 제거되는 순서를 (N, K)-요세푸스 순열이라고 한다. 예를 들어 (7, 3)-요세푸스 순열은 <3, 6, 2, 7, 5, 1, 4>이다.

N과 K가 주어지면 (N, K)-요세푸스 순열을 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 N과 K가 빈칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000)

 

출력

예제와 같이 요세푸스 순열을 출력한다.

 

코드

#include <iostream>
#include <vector>

using namespace std;

int N;
int K;
vector<int> list;
vector<int> answer;

// 1번부터 N번까지의 사람을 추가
void init()
{
	int i;

	for (i = 1; i <= N; i++)
		list.push_back(i);
}

// 아무도 남아 있지 않을 때까지 K번째 사람을 제거
void josephus()
{
	int i = 0;
	int k = 1;

	// 아무도 남아 있지 않을 때까지
	while (!list.empty())
	{
		// 원형이므로 마지막 사람 다음은 첫 번째 사람
		if (i == list.size())
		{
			i = 0;
		}
		// K번째 사람을 제거하고 그 자리부터 다시 셈
		// i를 증가시키지 않고 k를 초기화
		if (k == K)
		{
			k = 1;
			answer.push_back(list[i]);
			list.erase(list.begin() + i);
		}
		// 다음 사람을 확인
		else
		{
			i++;
			k++;
		}
	}
}

// (N, K) - 요세푸스 순열을 출력
void print_per()
{
	int i;

	cout << "<";
	for (i = 0; i < answer.size() - 1; i++)
	{
		cout << answer[i] << ", ";
	}
	cout << answer[i] << ">" << endl;
}

int main()
{
	cin >> N >> K;
	init();
	josephus();
	print_per();
	return 0;
}

 

문제 유형은 큐를 사용하는 것이라고 적혀있지만 벡터를 사용해서 풀이했다. 원리는 큐를 사용할 때와 동일하다.

만약 큐를 사용하려면 1부터 N까지 차례대로 큐에 저장한 후, K번째 사람이면 맨 앞에 있는 값을 출력하고 아니면 맨 앞에 있는 값을 다시 큐에 삽입하면 된다.

 

링크

1158번: 요세푸스 문제

inbdni/Baekjoon