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

문제

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

백준 20301

 

문제 내용

1~N번까지의 사람이 원을 이루며 앉아있고, 계속해서 K번째 사람을 지워나가면 된다.

이때, M명의 사람이 제거될 때마다 방향을 바꿔나가면 된다.

문제에서는 사람을 지워나가는 순서를 출력하기를 바란다.

 

아래 링크는 백준 1158 요세푸스 문제이다.

이 문제에서 'M명의 사람이 제거될 때마다 방향을 바꾼다'라는 조건을 추가하면 지금 풀고자 하는 문제가 된다.

https://gyong0117.tistory.com/entry/BOJ%EB%B0%B1%EC%A4%80-1158C-%EC%9A%94%EC%84%B8%ED%91%B8%EC%8A%A4-%EB%AC%B8%EC%A0%9C

 

문제 풀이

백준 1158 요세푸스 문제는 queue로 풀면 됐었다.

하지만 이 문제는 deque를 이용해야 한다.

deque는 queue와 stack의 장점을 모두 가지고 있다는 특징이 있다.

deque는 양 끝에서 push, pop이 모두 가능하다.

이 문제에서는 방향을 바꿔가며 사람을 삭제해야 하기 때문에 deque를 사용해야 한다.

 

먼저, 1~n을 담은 deque를 만든다.

이후, 순방향일 때는 앞에서 k-1명을 pop 하고 뒤에 push 하면 된다.

그럼 deque의 front에는 우리가 제거해야 할 k번째 사람이 남는다.

이를 출력해주면 된다.

 

역방향일 때는, 뒤에서부터 k-1명을 pop 하고 앞에 push 해주면 된다.

deque의 back에는 우리가 제거하고자 하는 k번째 사람이 남는다.

이를 출력해주면 된다.

 

사람 한 명을 제거할 때마다, count변수의 값을 늘려준다.

count의 값이 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;
	cin >> n >> k>> m;

	deque<int>dq;
	for (int i = 1; i <= n; i++) dq.push_back(i);


	//문제 해결
	int count = 0;
	bool check = true;
	while (!dq.empty()) {
		if (check) { //앞을 빼서 뒤에 넣는다.
			for (int i = 0; i < k - 1; i++) {
				dq.push_back(dq.front());
				dq.pop_front();
			}
			cout << dq.front() << '\n';
			dq.pop_front();
		
		}else{ //뒤를 빼서 앞에 넣는다.
			for (int i = 0; i < k - 1; i++) {
				dq.push_front(dq.back());
				dq.pop_back();
			}
			cout << dq.back() << '\n';
			dq.pop_back();
		}
		count++;
		if (count == m) {
			check = !check;
			count = 0;
		}
	}

}