백준 11866 - 요세푸스 문제 0

이 문제는 다양한 방식을 이용해 해결할 수 있습니다. 큐를 이용해 해결하거나, 원형 연결리스트를 이용해 해결할수도 있습니다. 저는 단순히 배열을 이용해 해결했습니다.

#include <iostream>

int main()
{
	std::cin.tie(NULL);
	std::ios_base::sync_with_stdio(false);

	int n, k;
	std::cin >> n >> k;

	int* nums = new int[n + 1];
	int* results = new int[n + 1];
	int resultCnt = 0;
	for (int i = 0; i <= n; i++)
	{
		nums[i] = i;
	}

	int check = 0;
	for (int i = 0; i < n; i++)
	{
		int notcnt = 0;
		int cnt = 1;

		while (cnt != k || nums[(check + cnt + notcnt) % n] == -1)
		{
			if (nums[(check + cnt + notcnt) % n] == -1)
				notcnt++;
			else
				cnt++;
		}

		check = check + cnt + notcnt;

		int pos = check % n;
		nums[pos] = -1;
		if (pos == 0)
			results[resultCnt++] = n;
		else
			results[resultCnt++] = pos;
	}
	std::cout << "<";
	for (int i = 0; i < resultCnt; i++)
	{
		std::cout << results[i];
		if (i != resultCnt - 1)
			std::cout << ", ";
	}
	std::cout << ">";

	return 0;
}