[C++] BOJ 1158 요세푸스 문제

문제

백준 1158번 요세푸스 문제

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

1158번: 요세푸스 문제

코드

#include<iostream>
#include<deque>
using namespace std;
int n, k;
int main() {
	cin >> n >> k;
	deque<int> d;
	for (int i = 1; i <= n; i++)d.push_back(i);
	cout << "<";
	while (d.size()>1) {
		int cnt = k-1;
		while (cnt--) {
			d.push_back(d.front());
			d.pop_front();
		}
		cout << d.front() << ", ";
		d.pop_front();
	}
	cout << d.front() << ">";
}

풀이방법

원을 이뤘다는 성질을 이용한다. (k-1)번동안은 사람을 그냥 맨 뒤로 보내고, k번째 사람은 제거한다. 맨 뒤로 보낼 때에는 front를 push_back해주고 pop_front를 해준다. 제거할 때는 front를 출력해주고 pop_front를 한다.

고민과정

원이라길래 복잡하게 mod연산자까지 생각하다가 deque를 이용하면 된다는 사실을 깨달았다. 출력방식(< , >)을 제대로 맞추지 않아서 틀렸었다. 세상에나