BOJ/백준 - 1158 요세푸스 문제 C++

큐를 알고있다면 쉽게 풀 수 있는 문제이다.

K만큼 앞에서 뺐다가 뒤로 다시 넣는 식으로 원을 이루고 앉아있는 것처럼 구현한다.

#include <iostream>
#include <queue>
using namespace std;

queue <int> q;
vector <int> ans;
int main() {
	int N, K;

	cin >> N >> K;
	
	for (int i = 1; i <= N; i++) {
		q.push(i);
	}

	while (!q.empty()) {
		int i = K-1;
		while (i != 0) { //K만큼 앞에서 뺐다가 뒤로 다시 넣는다.
			int tmp = q.front();
			q.pop();
			q.push(tmp);
			--i;
		}
		int ans_num = q.front();
		q.pop();
		ans.push_back(ans_num); //빠진 수를 vector ans에 push한다.
		
	}

	cout << "<";
	for (int i = 0; i < N-1; i++) {
		cout << ans[i] << ", ";
	}
	cout << ans[N - 1] << ">";

	return 0;
}