요세푸스 문제 0 (feat. 백준, 11866번)

요세푸스 문제 0
https://www.acmicpc.net/problem/11866

11866번: 요세푸스 문제 0

 

반응형

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
#include <deque>
#include <queue>
using namespace std;
int main() {
	ios::sync_with_stdio(false), cin.tie(NULL);
	deque<int> tmp;
	queue<int> ans;
	register int N, K, idx = 0;
	cin >> N >> K;
	for (register int i = 1; i <= N; ++i)
		tmp.push_back(i);
	while (!tmp.empty()) {
		idx += K - 1;
		idx %= tmp.size();
		ans.push(tmp.at(idx));
		tmp.erase(tmp.begin() + idx);
	}
	cout << "<";
	while (!ans.empty()) {
		if (ans.size() == 1)
			cout << ans.front();
		else
			cout << ans.front() << ", ";
		ans.pop();
	}
	cout << ">";
	return 0;
}
// *&)*@*

1. 자료구조 deque에 주어진 1 ~ N을 삽입합니다.
2. K만큼 인덱스를 증가시키고 deque의 길이만큼 나머지를 구합니다.
3. 자료구조 queue에 deque의 인덱스 값을 삽입합니다. 그리고 deque에서 삽입한 값을 삭제합니다.
4. 위 과정은 deque가 empty일때까지 반복합니다.
5. 입력된 queue를 front부터 출력합니다.