백준 BOJ 11025 요세푸스 문제 3

풀이를 안 보고 풀진 못 했다.

해답이 많이 올라와 있지만 스스로 정리를 하며 기억하기 위해 작성해본다.

---

 

1. 문제

https://www.acmicpc.net/problem/11025

11025번: 요세푸스 문제 3

 

1번부터 N번까지 원형으로 앉아있고 K번째 마다 제거 할 때, 마지막에 남은 번호를 구하는 문제.

 

1 <= K <= N <= 5,000,000 의 조건이라 곧이곧대로 풀면 시간초과가 나기 때문에 아이디어가 필요하다.

 

 

2. 풀이

 

문제의 과정을 1부터 N까지 큐에 넣고 K번째 마다 제거 나머지는 다시 큐에 넣는다고 생각하자.

N=7, K=3 일 때 첫 원소를 제거한 큐의 모습은 아래와 같을 것이고 이 큐를 X라 하자.

N=6, K=3 일 때 초기 상태의 큐는 아래와 같고 이 큐를 Y라 하자.

4 5 6 7 1 2 // N=7, K=3  큐 X
1 2 3 4 5 6 // N=6, K=3  큐 Y

 

X의 모습과 Y의 모습을 잘 살펴보면 아래와 같은 수식으로 나타낼 수 있는 관계가 됨을 알 수 있다.

X[i] = (( Y[i] + 3 - 1 ) % MOD 7 ) + 1

=> X[i] = ((Y[i] + K - 1 ) % MOD N)  + 1

( 3을 더하고 7을 바로 나누지 않는 이유는 4 -> 7이 성립하지 않아서 이고 보완하기 위해 -1 이후 +1을 해준다. )

 

결국 마지막에 남는 숫자를 f(N, K) 라고 할 때 다음의 점화식이 성립한다.

f(N,K) = (( f(N-1, K) + K - 1 ) % MOD N ) + 1

f(1,K)는 1임을 알 수 있고

f(1, K)로 f(2,K)를 구할 수 있고 f(2,K)로 f(3,K) ... 반복하면 f(N,K)를 구할 수 있다.

 

 

3. 코드

c++

#include<iostream>
#define INF 1e9
using namespace std;
using lld = long long int;
using pii = pair<int, int>;


int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n, k;
    cin >> n >> k;
    
    int ans = 1;
    
    for(int i=2; i<=n; i++) {
        ans = ((ans + k - 1) % i) + 1;
    }
    
    cout << ans;

    return 0;
}

 

python

n,k = map(int, input().split())

ans = 1
for i in range(2, n+1):
    ans = ((ans + k - 1) % i) + 1
    
print(ans)