1158번: 요세푸스 문제

메모리

시간

1228 KB

64 ms

문제 풀이

요세푸스 문제는 주어진 수 n를 둥글게 나열한 뒤 k 번째의 수를 순서대로 출력하는 문제이다.

단순하게 큐를 사용하면 쉽게 풀수 있다.

큐에 n의 수를 순서대로 넣고 k - 1 만큼 다시 큐의 뒤에 넣어주고 k 번째 수를 pop 하면

순열을 구할 수 있다.

Code

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

int main()
{
	int n,k;
	scanf("%d%d", &n, &k);
	queue <int> que;

	int i = 0;
	for (int i = 1; i <= n; i++)
	{
		que.push(i);
	}
	printf("<");
	while (!que.empty())
	{
		for (int i = 0; i < k - 1; i++)
		{
			int a = que.front();
			que.push(a);
			que.pop();
		}
		if (que.size() == 1)
			printf("%d", que.front());
		else
			printf("%d, ", que.front());
		que.pop();
	}
	printf(">");
	return 0;
}