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