[백준 20301] 반전 요세푸스

문제

www.acmicpc.net/problem/20301

20301번: 반전 요세푸스

 

풀이

기존의 요세푸스 문제는 항상 원소가 제거되는 방향이 앞에서 뒤로 일정하여 큐를 사용할 수 있었지만, 이 문제에선 반대 방향도 존재하기때문에 편의를 위해 덱을 사용하여 해결할 수 있습니다. (물론 큐를 사용하여 방향이 바뀔 때마다 큐를 역순으로 바꿔서 해결할 수도 있습니다.) 

---

1. 방향과 상관없이 앞에서 뒤(뒤에서 앞)으로 k번째 사람을 제거하므로 k - 1번 사람을 뒤로 넘기거나 앞으로 넘겨주고 k번 사람을 제거합니다.

 

2. 그렇게 제거한 사람의 수가 M이 될 때마다 방향을 바꿔주면 됩니다.

 

풀이

#include <bits/stdc++.h>
using namespace std;

int n, m, k, die, cnt;
bool r;
deque<int> dq;

int main() {
	cin.tie(NULL); cout.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> n >> k >> m;
	for (int i = 1; i <= n; i++) dq.emplace_back(i);
	while (!dq.empty()) {
		cnt = k - 1;
		if (!r) {
			while (cnt--) {
				dq.emplace_back(dq.front());
				dq.pop_front();
			}
			cout << dq.front() << '\n';
			dq.pop_front();
		}
		else {
			while (cnt--) {
				dq.emplace_front(dq.back());
				dq.pop_back();
			}
			cout << dq.back() << '\n';
			dq.pop_back();
		}
		if (m == ++die) r = 1 - r, die = 0;
	}
}