문제요약

문제

1. A, B 두사람이 $n \le 10^{15}$개의 동전을 가지고 게임을 한다. (A먼저)
2. 맨 처음 A는 1~n개의 동전을 가져갈 수 있고, 그 다음 사람은 그 전 사람이 가져간 동전 개수의 2배 이하 개수만큼 가져갈 수 있다. (0개 가져갈 수는 없다)
3. 마지막 동전 가져가는 사람이 이긴다.
4. 두 사람 모두 최선을 다한다.

이때, A가 이기기 위해 가져가야 할 첫턴의 동전 개수의 최솟값을 구해야 한다.

풀이

명제 + 기본적 풀이

n보다 작거나 같은 가장 큰 피보나치 수를 f(n)이라고 하자. 이때, 다음 두가지가 성립한다.

1. n > f(n)이면, (n일때의 답) = (n - f(n)일때의 답)이다.
2. n = f(n)이면, f(n)이 답이다.

따라서, $10^{15}$까지의 피보나치 수를 구하고, n에 대해서 f(n)을 계속 구해주면 된다. n > f(n)이면 n-=f(n)을 해주고, n = f(n)이면, f(n)을 답으로 출력하면 된다.

증명

dp[i][j]를 동전 i개가 남았고, 이전 사람이 j개의 동전을 가져갔을 때 턴인 사람이 이기면 1, 지면 0이라고 하자.

dp[i][j]를 손으로 구해보면 다음과 같은 결과를 얻을 수 있다. 다음 표에서 빈칸은 1이다.

3, 5, 8, …행 등등 피보나치 수 행에서 0이 길게 적힌다는 것을 알 수 있다. 위에서 다음과 같은 사실을 유추할 수 있다. f(i)를 i번째 피보나치수라고 하자. f(i) > 3을 만족하는 i에 대해서, 다음 두 사실이 성립한다.

1. f(i) < x < f(i + 1)을 만족하는 x에 대해서 dp[x][?]은 dp[x - f(i)][?]과 같다.
2. dp[f(i+1)][j] = 0을 만족하는 j는 j <= int((f(i+1) - 1) / 2) 이다.

처음 시작하는 A의 입장에서는 dp[n - x][x] = 0을 만족하는 가장 작은 x를 찾아야 한다.

여기까지 하고 증명 좀 더 적기 힘들다 ㅠㅠ 말로 표현하는거가 너무 힘들다.

코드

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
LL t[1000];
int main(){
    LL n;
    t[1] = 1LL;
    t[2] = 2LL;
    int i;
    scanf("%lld",&n);
    for(i=3;;i++){
        t[i] = t[i-2] + t[i-1];
        if(t[i] > 1e15) break;
    }
    for(;i && n;i--){
        if(n >= t[i]){
            n-=t[i];
        }
    }
    printf("%lld\n",t[i + 1]);
    return 0;
}

성찰

이 문제는 풀이를 보고 그 풀이를 증명하려고 노력했다. 증명이 엄밀하지 않아서 더 생각하고 싶다.