목차

수학 게임

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

게임 이론

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

풀이

코드

"""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()