반 년 넘게 백준 시도했지만 맞지 못한 문제 칸에서 방 뺄 생각을 하지 않는 요세푸스 문제 2를 해결하기 위해 1시간 넘게 시도하다가 포기하고 대신 풀은 문제이다.
요세푸스 문제에 대해 여러 가지 알아보다가 쉽게 푼 문제인데 아무것도 모르는 상태에서 풀라면 절대로 풀지 못했을 문제라고 생각한다....
실제로 백준 고수님들도 난이도 기여에서 이 문제에 플레 이상을 주셨다.
그래서 문제에서 점화식을 뽑아내는 과정에 대해 리뷰해보려한다.
문제링크
https://www.acmicpc.net/problem/11025
설명
요세푸스 문제에서 n과 k가 주어질 때, 마지막까지 남는 번호를 구하는 문제이다.
일단 n = 7, k = 3이고 큐를 이용해 풀이를 한다 가정해보자.
번호를 뽑는 첫번째 과정을 실행한 후 큐 상태는 다음과 같을 것이다.
3을 뽑고 난 뒤 큐 상태 : 4 5 6 7 1 2
그리고 그 다음 다시 3번째 번호를 뽑는 과정을 진행할 것이다.
이때 이 과정을 자세히 살펴보면 n = 6, k = 3일 때의 첫번째 과정을 실행하는 것과 유사한 것을 확인할 수 있다.
1) 4 5 6 7 1 2 // n = 7, k = 3일 때 두번째 번호를 뽑기 전 큐 상태
2) 1 2 3 4 5 6 // n = 6, k = 3일 때 첫번째 번호를 뽑기 전 큐 상태번호만 다를 뿐 3번째 번호를 뽑는다는 사실에는 변함이 없다.
위 과정에서 다음과 같은 관계를 알아낼 수 있다.
1)의 큐가 X이고 2)의 큐가 Y라고 할 때,
X[i] = ((Y[i] + 3 - 1) % 7) + 1그냥 3을 더하고 7로 나누지 않는 이유는 4 -> 7이 성립하지 않기 때문이다.
위 식에서 3은 k이고 7은 n이므로, 다음과 같은 점화식을 구할 수 있다.
f(n, k)이 마지막으로 남는 번호라고 할 때,
f(n, k) = ((f(n - 1, k) + k - 1) mod n) + 1위 과정을 계속 반복하다보면 n이 1이 되는데 f(1, k)는 당연히 1이므로 f(n, k)를 쉽게 구할 수 있다.
점화식도 뽑았으니 DP를 이용해 코드를 작성하면 되는데 이 때 유의해야 할 점이 있다.
n이 최대 5백만이므로, top-down 방식이나 배열을 활용하면 메모리 초과가 발생할 수도 있음
bottom-up 방식으로 이전의 결과만 가지고 n까지 DP를 실행하면 O(n)의 시간복잡도로 이 문제를 해결할 수 있다.
코드
#include <iostream>
using namespace std;
int n, k, ans = 1;
void solve()
{
cin >> n >> k;
for (int i = 2; i <= n; i++)
ans = (ans + k - 1) % i + 1;
cout << ans;
}
int main(void)
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
solve();
return 0;
}