들숨날숨

[C/C++]백준 20301

 
  • Mar 08, 2021

백준 20301 - 반전 요세푸스 문제 (실버5)

10819 문제 링크

요세푸스 문제는 다음과 같다. 1번 사람 오른쪽에는 2번 사람이 앉아 있고, 2번 사람 오른쪽에는 3번 사람이 앉아 있고, 계속하여 같은 방식으로 N명의 사람들이 원을 이루며 앉아 있다. N번 사람 오른쪽에는 1번 사람이 앉아 있다. 이제 K번 사람을 우선 제거하고, 이후 직전 제거된 사람의 오른쪽의 K번째 사람을 계속 제거해 나간다. 모든 사람이 제거되었을 때, 제거된 사람의 순서는 어떻게 될까?
이 문제의 답을 (N,K)요세푸스 순열이라고 하며, (7,3)요세푸스 순열은 <3,6,2,7,5,1,4>가 된다.
이 요세푸스 문제에서 M명의 사람이 제거될 때마다 원을 돌리는 방향을 계속해서 바꾸려고 할때, 이때의 답을 (N,K,M) 반전 요세푸스 순열이라고 한다. (7,3,4) 반전 요세푸스 순열은 <3,6,2,7,1,5,4>가 된다.
#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <cstring>
#include <stack>
#include <queue>
#include <deque>
using namespace std;
deque <int> dq;
int n, m, k;
void ctrClockwise(int k_count, int m_count);
void Clockwise(int k_count, int m_count) { //요세푸스순열
	if (dq.empty()) return;
	if (k_count == k) {
		printf("%d\n", dq.front());
		dq.pop_front();
		if (m == m_count + 1) {//m번만큼 제거되면 반전요세푸스로 바꿔준다.
			ctrClockwise(1, 0);
		}
		else {
			Clockwise(1, m_count + 1);
		}
	}
	else {
		dq.push_back(dq.front());
		dq.pop_front();
		Clockwise(k_count + 1, m_count);
	}
	return;
}
void ctrClockwise(int k_count, int m_count) { //반전요세푸스 순열
	if (dq.empty()) return;
	if (k_count == k) {
		printf("%d\n", dq.back());
		dq.pop_back();
		if (m_count + 1 == m) { //m번만큼 제거되먼 요세푸스로 바꿔준다.
			Clockwise(1, 0);
		}
		else {
			ctrClockwise(1, m_count + 1);
		}
	}
	else {
		dq.push_front(dq.back());
		dq.pop_back();
		ctrClockwise(k_count + 1, m_count);
	}
	return;
}
int main() {
	scanf("%d %d %d", &n, &k, &m);
	for (int i = 1; i <= n; i++) {
		dq.push_back(i);
	}
	Clockwise(1, 0);
}
Search