[Baekjoon/백준] 11866번: 요세푸스 문제 0(C/C++)

단계별로 풀어보기 19단계(큐, 덱) 3번 문제

https://www.acmicpc.net/step/12

큐, 덱 단계

---

백준 11866번: 요세푸스 문제 0

https://www.acmicpc.net/problem/11866

11866번: 요세푸스 문제 0

---

문제 설명

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

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 ≤ 1,000)

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

---

접근 방법

이번 문제는 사람 수 N과 양의 정수 K를 입력받아 요세푸스 순열을 출력하는 문제다. 요세푸스 순열이란 1~N까지 N명의 사람을 원으로 두고 K번째 사람을 계속해서 제거해 모든 사람을 제거한 그 순서를 순열로 한 것이다.

사람들이 1~N까지 줄 서 있고 1부터 시작해서 K-1번까지는 원형 줄이므로 뒤로 보내야한다. 지난 카드 문제와 유사한 내용이므로 역시 큐로 문제를 풀면 된다. 앞에서 K-1번까지 뒤로 보내는 것은 반복문에서 큐의 front 값을 push하고, pop하는 방식으로 진행하고, 이후 K번 값은 pop하는 것을 반복하면 된다. 출력 방식에서 쉼표와 괄호를 추가해야하므로 이를 유의하면서 코드를 작성하면 문제를 해결할 수 있다.

---

코드

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

queue<int> q;

int main(int argc, char *argv[]) {
	int N, K;

	cin >> N >> K;

	for (int i = 1; i <= N; i++)
		q.push(i);

	cout << "<";
	while (q.size() > 0) {
		for (int i = 0; i < K - 1; i++) {
			q.push(q.front());
			q.pop();
		}

		cout << q.front();
		q.pop();
		
		if (q.size() > 0)
			cout << ", ";
	}

	cout << ">" << endl;

	return 0;
}

---

결과

백준 제출 결과

진짜 쉬운 문제인데 바보같이 K를 예제 숫자인 3으로만 생각하고 while문에서 pop을 2번만 했어서 틀렸었다..