[Baekjoon, C++] 11866번 : 요세푸스 문제 0

백준 단계별 풀기에서 큐,덱 세 번째 문제이다.

링크는 아래와 같다.

www.acmicpc.net/problem/11866

11866번: 요세푸스 문제 0

---

백준 11866번 문제, 입력, 출력

---

백준 11866번 입출력 예제 1

---

circular queue 구조

1. 원을 이룬다는 것은 Circular Queue를 생각하면 된다. 논리상 구조는 실질적으로 인덱스 0과 7이 붙어 있지는 않지만 붙어있는 것처럼 간주하겠다는 것이다. 

 

2. 요세푸스 문제를 예로, N=3 이라면 3, 6, 9, 12 의 순서대로 정수값들을 뺀다. 그렇다면, queue의 front값을 읽어 해당 순서를 제외하고는 다시 queue에 넣어주면 된다. 3 6 9 번째 숫자들은 출력을 해주고 pop을 통해 빼준다. 이것을 반복하면 결국엔 큐에 아무것도 남지 않게 된다. 

---

 

#include<iostream>  
#include<queue>

using namespace std;

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	int numOfSeq;
	int numOfExit;
	queue<int> que;

	cin >> numOfSeq;
	cin >> numOfExit;

	for (int i = 1; i <= numOfSeq; i++) {
		que.push(i);
	}

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

		if (!que.empty()) {
			cout << ", ";
		}
	}
	cout << ">";
	
	return 0;
}