[LeetCode] 1823. Find the Winner of the Circular Game

문제 링크

해당 주차 수업이 Recursion에 관한 것이어서 처음에는 재귀로 풀어보려 했는데, 도저히 어려워서 queue를 사용해서 코드를 작성하고 발표를 했다. 큐에서 하나씩 pop해서 pop한 애가 탈락해야할 애가 아니면 다시 queue에 push해줬고, 탈락해야할 아이면 pop해주면서 queue에 하나만 남을 때까지 진행하면 된다.

그치만 언젠간 재귀로 풀어야 한다..!

재귀를 이용한 풀이

f(n, k): the survivor given n and k

만약에 f(n-1, k)를 알고 있을 때, f(n, k)를 어떻게 구할 것인가?

EX)
1. f(4,2)일 때, 0번 째 사람이 살아남으므로 f(4,2)=0이다.
2. 만약 n=5인 경우, 우선 1번 째 사람이 먼저 탈락하고, 남은 사람들은 2, 3, 4, 0, 총 4명이 남는다.
3. 그러면 여기서 f(4,2) = k+0 = 2+0 = 2가 살아남을 것이다.

다시 정리하면, n이 주어지고, f(n-1, k)를 알 때, 우선 k-1번 째 사람이 먼저 탈락하고, 남은 사람들은 k, k+1, ...(k+n-2) % n, 총 n-1명이다. 그러면 k+f(n-1,k)번째 사람이 살아남을 것이다.

따라서 f(n, k) = (k+f(n-1, k)) % n 이 성립되고, 코드를 작성하면 다음과 같다.

int recursion(int n, int k){
    if(n==1) return 0;
    return (k+recursion(n-1, k))%n;
}

int findTheWinner(int n, int k){
    return recursion(n, k)+1;
}