백준 1158번: 요세푸스 문제(C++)

www.acmicpc.net/problem/1158

1158번: 요세푸스 문제

코드

#include <iostream>
using namespace std;

bool check[5001] = {0, };
int n, k;

void solve(int idx, int cnt){
	if(cnt == n){
		cout << idx << ">" << endl;
		return;}
	else {
		cout << idx << ", ";
		check[idx] = 1;
	}
	int cycle = 0;
	
	while(cycle != k){
		if(++idx == (n + 1)) idx = 1;
		if(check[idx] == true) continue;
		else cycle++;
	}
	
	solve(idx, cnt+1);
}

int main() {
	cin >> n >> k;
	cout << "<";
	solve(k, 1);
	return 0;
}

풀이

분류를 보니 큐를 사용해서 풀어야 하는 문제였던 것 같다.

하지만 지금 나는 큐를 배웠던 기억이 아주 어렴풋 하게 있고... 큐를 사용해서 풀진 않았다.

어떻게 보면 DFS? BFS? 같은 방식으로 재귀함수를 사용해서 풀었다.

출력이 중복된 수는 안 나오며, 자연수 1부터 주어진 수 N까지의 모든 수가 하나씩 나온다는 것에 기인했다.

check 배열을 하나 만들어서 그 수가 나오면 체크를 하고 그 자리 수는 무시해서 다음 K번째 순서를 찾는다.

그렇게 찾은 횟수가 N번이 되면 끝나는 방법이었다.

 

나중에 자료구조를 배워서 Q 컨테이너를 사용해서 풀어봐야겠다.