사용자 도구

사이트 도구


ps:problems:boj:2862

수학 게임

ps
링크acmicpc.net/…
출처BOJ
문제 번호2862
문제명수학 게임
레벨플래티넘 1
분류

게임 이론

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

풀이

  • Fibonacci Game에서 N이 더 커진 버전. Fibonacci Game에서는 첫턴에 최대 N-1개의 돌을 가져갈수 있었고, 그래서 이길수 없는 경우에는 -1을 출력하도록 되어있었지만, 여기에서는 최대 N개의 돌을 가져갈수 있기때문에 이길수 없는 경우는 생기지 않는다. 하지만 이길수 있는 경우에는 최소의 돌을 가져가는 방법만 출력하라고 되어있으므로, 결과적으로 출력해야 하는 값은 이길수 없을때 -1 대신 N을 출력한다는 것을 제외하고는 동일하다.
  • 풀이는 Fibonacci Game과 동일.

코드

"""Solution code for "BOJ 2862. 수학 게임".

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

Tags: [number 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())
    print(zeckendorf_representation(N)[-1])


if __name__ == '__main__':
    main()

토론

댓글을 입력하세요:
Q U R D W
 
ps/problems/boj/2862.txt · 마지막으로 수정됨: 2023/06/15 14:13 저자 teferi