사용자 도구

사이트 도구


ps:problems:boj:2373

Fibonacci Game

ps
링크acmicpc.net/…
출처BOJ
문제 번호2373
문제명Fibonacci Game
레벨플래티넘 1
분류

게임 이론

시간복잡도O(logn)
인풋사이즈n<=1,000,000
사용한 언어Python 3.11
제출기록31256KB / 48ms
최고기록36ms
해결날짜2023/06/15

풀이

  • 게임규칙을 분석해서 바로 승리전략을 파악하는 것은 사실 쉽지 않고, 그래서 이런 경우에 늘 하듯이 DP를 이용해서 결과를 일일히 계산해보는 것이 정석이다. 이 문제는 N이 작기 때문에, DP를 통해서 답을 계산할수 있다. 하지만, 작은 N값들에 대해서 결과를 나열해보면 규칙성을 찾는것도 어렵지 않다.
    • 수학 게임는 동일한 규칙이지만, N의 범위가 커졌기 때문에 규칙성을 찾아야만 풀수 있다.
  • 하지만, 사실 이 게임은 Fibonacci nim이라는 유명한 게임을 그대로 옮겨온 것이다. 그리고 위키피디아 링크에는 이 게임에 대해 전부 분석되어 있다.
    • 처음 주어진 수가 피보나치 수가 아니라면 선공에서 필승법이 존재한다
    • 필승 전략은 주어진 수를 zeckendorf representation로 나타냈을때, 가장 작은 자리의 피보나치수만큼을 제거하는 것이다.
    • 전략을 알고 나면, 이유를 분석하는 것은 가능하다. 내 차례에 가장 작은 자리의 피보나치 수 x를 제거해서 상대에게 넘겨주면, 그 다음 작은 자리의 피보나치 수는 x*2보다 크기때문에, 상대방은 그 다음 작은 자리의 피보나치 수를 제거할 수 없다.
  • 결국 문제의 답은, 주어진 수를 zeckendorf representation으로 변환한 뒤에 가장 작은 자리의 피보나치 수를 출력하면 된다. 주어진 수가 피보나치 수라면, -1을 출력한다
  • zeckendorf representation은 그리디한 방법으로 O(logn)에 구할수 있다.

코드

"""Solution code for "BOJ 2373. Fibonacci Game".

- Problem link: https://www.acmicpc.net/problem/2373
- Solution link: http://www.teferi.net/ps/problems/boj/2373

Tags: [game theory]
"""


def zeckendorf_representation(n):
    ret = []
    a, b = 1, 1
    while b <= n:
        a, b = b, a + b
    while n:
        while a > n:
            a, b = b - a, a
        n -= a
        ret.append(a)
    return ret


def main():
    N = int(input())
    zr = zeckendorf_representation(N)
    print('-1' if len(zr) == 1 else zr[-1])


if __name__ == '__main__':
    main()

토론

댓글을 입력하세요:
V᠎ F O C K
 
ps/problems/boj/2373.txt · 마지막으로 수정됨: 2023/06/15 14:39 저자 teferi