[백준 C++] 11866 : 요세푸스 문제 0

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

solved.ac Class 2 에센셜에 포함되어 있는 구현 문제이다.

---

#include <iostream>
#include <vector>

using namespace std;

int main()
{
	int list[1001] = { 0, };
	int N, K;
	cin >> N >> K;

	int idx = K;

	vector<int> ans;

	for (int i = 1; i <= N; i++)
		list[i] = i;

	while (true)
	{
		if (list[idx] != 0)
		{
			ans.push_back(idx);
			list[idx] = 0;
		}

		if (ans.size() >= N)
			break;
		else
		{
			int move = 0;
			while (move < K)
			{
				if (idx + 1 > N)
					idx = 1;
				else
					idx += 1;

				if (list[idx] != 0)
					move++;
			}
		}
	}

	cout << '<';
	for (int i = 0; i < ans.size() - 1; i++)
		cout << ans.at(i) << ", ";
	cout << ans.back() << ">\n";

	return 0;
}

while문 안에 while문이 또 있어 시간복잡도가 좋지는 않지만, N의 최댓값이 1000이므로 시간 초과가 뜰 일은 없다.

idx를 이용하면서 방문함과 동시에 값이 0(갈 필요가 없거나, 이미 들렸거나)인지를 확인하면서 move 변수를 이용해 순차적으로 이동하였다.