BOJ

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

정영주 2021. 5. 9. 16:38

문제 출처 : BOJ 1158 - 요세푸스 문제 www.acmicpc.net/problem/1158

 

저번에 큐로 풀었던 요세푸스 문제이다.

이번에는 list를 이용하여 풀어보았다.

 

최종 코드

#include <iostream>
#include <list>

using namespace std;

int main() {
	int n, k, cnt = 0;
	cin >> n >> k;

	list<int> L;

	for (int i = 1; i <= n; i++)
		L.push_back(i);

	cout << '<';
	while (L.size() > 1) {
		if (++cnt == k) {
			cout << L.front() << ", ";
			L.pop_front();
			cnt = 0;
		}
		else {
			L.push_back(L.front());
			L.pop_front();
		}
	}
	cout << L.front() << ">" << '\n';

	return 0;
}

 

출력 형식을 맞추기 위해서

L에 원소가 하나만 남을 때까지 while문을 반복하고,

k번째마다 (if) 맨 앞 원소를 출력해준다.

k번째가 아니라면 (else) 맨 앞 원소를 맨 뒤로 옮겨준다.

 

list를 이용하면 이렇게 간단하게 요세푸스 문제를 풀 수 있다.