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

문제 링크

1158번: 요세푸스 문제

문제 요약

N명의 사람들이 원을 이루고 앉아있을 때, K번째 사람을 반복하여 제거해 만들 수 있는 (N, K)-요세푸스 순열을 구하는 프로그램을 작성한다.

접근 방법

큐를 이용해서 간단하게 풀 수 있습니다.

1. 1부터 N까지의 수를 순서대로 큐에 삽입한다.
2. 큐가 빌 때까지 다음의 절차를 반복한다.

• 큐의 front의 원소를 큐에 삽입하고 제거하는 작업을 (K-1)번 반복한다.
• (K-1)번 반복을 마치면 현재 큐의 front의 원소가 (N, K)-요세푸스 순열의 현재 위치의 원소가 된다.
• 큐의 front의 원소를 출력하고, 제거해준다.

코드

#include <bits/stdc++.h>

using namespace std;

int main(void)
{
	int n, k;
	cin >> n >> k;

	queue<int> q;
	for (int i = 1; i <= n; i++)
		q.push(i);

	cout << '<';
	while (!q.empty())
	{
		for (int i = 0; i < k - 1; i++)
			q.push(q.front()), q.pop();

		cout << q.front();
		q.pop();

		if (!q.empty())
			cout << ", ";
	}
	cout << '>';

	return 0;
}