BOJ 1158 - 요세푸스 문제

• n, k(n, k<=5000)이 주어질 때 (n, k)-Josephus permutation을 구하는 문제이다.

문제 풀이

• n이 작아서 vector로 구현만해도 풀린다.

소스코드

#include<cstdio>
#include<vector>
using namespace std;

int main()
{
	int n, k, curk;
	scanf("%d %d", &n, &k);
	vector<int> sol, a(n);
	for(int i=0;i<n;i++) a[i]=i+1;
	curk=k;
	for(int i=n;i>0;i--){
		curk=curk%i;
		if(curk<=0) curk+=i;
		sol.push_back(a[curk-1]);
		a.erase(a.begin()+curk-1);
		curk=k-(i-curk);
	}
	printf("<");
	for(int i=0;i<sol.size()-1;i++) printf("%d, ", sol[i]);
	printf("%d>", sol.back());
}

풀고나서

• 1242번 문제랑 비슷한 문제이다. 둘 다 Josephus 순열에 관해 묻고 있는 문제이다. 하지만 1242번 문제에서는 M의 상대적 위치를 이용해서 답을 구했고 이 문제에서는 K의 상대적 위치를 바꿔가며 문제를 풀었다.

• 문제 자체는 쉽지만 만약 n, k가 10^6까지 간다면 쉽지 않을 것 같다. vector를 이용하면 O(N^2)이기 때문에 TLE이기 때문이다. erase가 Linear in the number of elements erased이고 random access가 가능한 STL을 쓰거나 어떻게 잘 풀어야 할 것 같다.