알고스팟 - 조세푸스 문제 (JOSEPHUS) [C++]

 동적 배열이나 리스트를 사용하는 문제지만, Queue로도 가능할 것 같아서 풀었다. N <= 1000 이고 K <= 1000 이므로 최악으로 잡아도 최대 연산이 1,000,000 밖에 안된다. 따라서 테스트 케이스 50번을 돌려도 1초 내에 돌아간다.

 

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

queue<int> makeQueue(int N) {
	queue<int> q;

	for (int i = 1; i <= N; i++) {
		q.push(i);
	}

	return q;
}

vector<int> solve(int N, int K) {
	queue<int> q = makeQueue(N);

	while (q.size() > 2) {
		q.pop();	// kill

		for (int i = 0; i < K - 1; i++) {
			int front = q.front();
			q.pop();
			q.push(front);
		}
	}

	vector<int> answer;

	while (!q.empty()) {
		answer.push_back(q.front());
		q.pop();
	}

	sort(answer.begin(), answer.end());

	return answer;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int C;
	cin >> C;

	for (int test = 0; test < C; test++) {
		int N, K;

		cin >> N >> K;

		vector<int> answer = solve(N, K);

		cout << answer[0] << " " << answer[1] << '\n';
	}

	return 0;
}