[백준] 알고리즘 C++ 11866번 - 요세푸스 문제 0문제

문제

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

11866번: 요세푸스 문제 0

소스코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
vector<int> ans;
queue<int> qu;
int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL); 
	int n, k;
	cin >> n >> k;
	for (int i = 1; i <= n; i++) {
		qu.push(i);
	}
	cout << "<";
	while (!qu.empty()) {
		for (int i = 1; i < k; i++) {
			qu.push(qu.front());
			qu.pop();
		}
		ans.push_back(qu.front());
		qu.pop();
	}
	for (int i = 0; i < ans.size(); i++) {
		if (i == ans.size() - 1) {
			cout << ans[i] << ">";
		}
		else {
			cout << ans[i] << ", ";
		}
	}
}

해설

요세푸스 문제들은 원을 이루며 사람을 없애거나 하는 그런 종류의 문제입니다.

즉 큐를 이용해서 해결할 수 있는데요

큐는 First in First out 구조를 가진 FIFO 먼저들어온 것이 먼저 나간다 라는 의미로써 사용됩니다.

즉 K번째가 되면 큐에서 삭제하고 출력해주는 것을 구하는 것입니다. 

소스코드를 보면 쉽게 이해가실 겁니다.