[ C / C++ ] 백준 20301 반전 요세푸스

문제

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

 1$1$번 사람 오른쪽에는 2$2$번 사람이 앉아 있고, 2$2$번 사람 오른쪽에는 3$3$번 사람이 앉아 있고, 계속하여 같은 방식으로 N$N$명의 사람들이 원을 이루며 앉아 있다. N$N$번 사람 오른쪽에는 1$1$번 사람이 앉아 있다. 이제 K$K$(≤N$\leq N$)번 사람을 우선 제거하고, 이후 직전 제거된 사람의 오른쪽의 K$K$번째 사람을 계속 제거해 나간다. 모든 사람이 제거되었을 때, 제거된 사람의 순서는 어떻게 될까?

이 문제의 답을 (N$\boldsymbol{N}$, K$\boldsymbol{K}$)–요세푸스 순열이라고 하며, (7$7$, 3$3$)–요세푸스 순열은 ⟨3,6,2,7,5,1,4⟩$\left<3, 6, 2, 7, 5, 1, 4\right>$가 된다.

하지만 한 방향으로만 계속 돌아가는 건 너무 지루하다. 따라서 요세푸스 문제에 재미를 더하기 위해 M$M$명의 사람이 제거될 때마다 원을 돌리는 방향을 계속해서 바꾸려고 한다. 이렇게 정의된 새로운 문제의 답을 (N$\boldsymbol{N}$, K$\boldsymbol{K}$, M$\boldsymbol{M}$)–반전 요세푸스 순열이라고 하며, (7$7$, 3$3$, 4$4$)–반전 요세푸스 순열은 ⟨3,6,2,7,1,5,4⟩$\left<3, 6, 2, 7, \mathbf{1}, \mathbf{5}, \mathbf{4}\right>$가 된다.

 N$N$, K$K$, M$M$이 주어질 때, (N$N$, K$K$, M$M$)–반전 요세푸스 순열을 계산해 보자.

 

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

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int N, K, M, cnt = 0;
	bool check;
	deque <int> d;
	cin >> N >> K >> M;
    
	for(int i = 1; i <= N; i++){
		d.push_back(i);
	}
    
	while(!d.empty()){
		if(check == 0){
			for(int i = 0; i < K - 1; i++){
				d.push_back(d.front());
				d.pop_front();
			}
			cout << d.front() << "\n";
			d.pop_front();
		}
		else{
			for(int i = 0; i < K - 1; i++){
				d.push_front(d.back());
				d.pop_back();
			}
			cout << d.back() << "\n";
			d.pop_back();
		}
		cnt++;
		if(cnt == M){
			check = !check;
			cnt = 0;
		}
	}
}