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

백준 단계별로 풀어보기 [큐, 덱] 요세푸스 문제 0

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

11866번: 요세푸스 문제 0

 

[풀이]

1~n까지의 배열에 대해 k 간격으로 삭제해나갈 때 삭제되는 수들의 배열이 요세푸스 순열이다. k의 간격만큼 큐에서 수를 맨 뒤로 보내고, 반복문이 끝나면 맨 앞에 있는 값을 새로운 배열에 저장한 후 pop한다. 큐가 비워질 때까지 반복한 뒤 요세푸스 순열이 저장된 배열을 출력한다.

 

[코드]

#include<iostream>
#include <queue>

int main() {
	//n, 간격 k에 대한 요세푸스 순열. 7 3 -> <3, 6, 2, 7, 5, 1, 4>
	int n, k;
	std::cin >> n >> k;
	std::queue<int> q;
	for (int i = 1; i <= n; i++) {
		q.push(i);
	}

	int* arr = new int[q.size()];
	int cnt = 0;

	int r;
	while (!q.empty()) {
		for (int i = 1; i < k; i++) {
			r = q.front();
			q.pop();
			q.push(r);
		}

		arr[cnt++] = q.front();
		q.pop();
	}

	std::cout << "<";
	for (int i = 0; i < cnt-1; i++) {
		std::cout << arr[i] << ", ";
	}
	std::cout << arr[cnt-1] << ">";

	delete[] arr;

}