[python][BOJ2373] Fibonacci Game

https://www.acmicpc.net/problem/2373

2373번: Fibonacci Game

 

 

생각이 어렵지 구현은 브론즈 수준이다. 직접 N값과 가져가는 값을 보면 가져갈 수 있는 값들은 늘 피보나치 수와 연관되어 있는 것을 알 수 있다. 이를 코드로 구현할 때 생각해야할 조건은 총 2개가 있다.

• N이 피보나치 수열의 수일 경우

        - 이 경우에는 무슨 짓을 해도 2번 사람을 이길 수가 없다. 계산할 필요 없이 -1을

          출력해주면 된다.

 

 

• N보다 작은 피보나치 수열중 가장 큰 값이 아닌 것을 가져가는 경우

        - 설명은 복잡하고 이해도 힘드므로 생략한다. 궁금한 사람은 구글에

           Zeckendorf's theorem을 검색해보길 바란다.

 

 

 

코드는 아래에 있다.

dp=[0,1]
for i in range(2,75):
    dp.append(dp[i-1]+dp[i-2])

c=int(input())
C=c
for i in range(74,2,-1):
    if c<dp[i]:
        continue
    elif c==dp[i]:
        break
    c-=dp[i]

print(-1 if c==C else c)

 

 

Zeckendorf's theorem 관련 문제에 관심이 있다면 수학 게임도 풀어보길 바란다.

https://www.acmicpc.net/problem/2862

2862번: 수학 게임