[백준(BOJ) 1158번] 요세푸스 문제 (C++)

문제 링크

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

 

문제 정보

입력

첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000)

출력

예제와 같이 요세푸스 순열을 출력한다.

 

풀이

 STL List의 erase 함수가 그 다음 원소의 위치를 반환한다는 것을 기억하고 있으면 해결 할 수 있는 문제다!

 

소스 코드

#include <bits/stdc++.h>
using namespace std;

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	int n; // 초기 인원수. 1 ~ n명
	int k; // 제거할 차례
	cin >> n >> k;
	
	list<int> L;
	for (int i = 1; i <= n; i++) {
		L.push_back(i);
	}
	auto cursor = L.begin();
	
	cout << '<';
	
	while (L.size() > 1) {
		// k 차례로 이동
		for (int i = 0; i < k - 1; i++) {
			cursor++;
			if (cursor == L.end()) {
				cursor = L.begin();
			}
		}
		
		cout << *cursor << ", "; // k번째 원소 출력
		
		cursor = L.erase(cursor);
		
		if (cursor == L.end()) {
			cursor = L.begin();
		}
	}
	
	cout << *cursor << '>';
	
	return 0;
}