Little Jay

[Python][Project Euler] 코딩퀴즈 6번 - 특정 구간내의 모든 피보나치 수의 합 본문

알고리즘/Project_Euler

[Python][Project Euler] 코딩퀴즈 6번 - 특정 구간내의 모든 피보나치 수의 합

Jay, Lee 2022. 2. 12. 14:31

피보나치 수에 대한 문제입니다. 피보나치 수는 아래와 같이 정의됩니다.
f(1) = 1
f(2) = 2
f(3) = f(1) + f(2) = 1 + 2 = 3
f(4) = f(2) + f(3) = 2 + 3 = 5
f(5) = f(3) + f(4) = 3 + 5 = 8
...
f(n) = f(n-2) + f(n-1), n>=3

a와 b라는 두 수가 주어져 있을 때 두 수 사이에는 몇 개의 피보나치 수가 있을까요?
예를 들어 10과 100 사이에는 총 5개(13, 21, 34, 55, 89)의 피보나치 수가 있고 모두 더한 값은 212입니다.

12345678999과 99987654321 사이에도 몇 개의 피보나치 수가 있습니다.
이 구간 내의 모든 피보나치 수를 더한 값이 기념품을 받을 수 있는 열쇠입니다 값은 얼마입니까?


출처) 풀면 기념품을 줬다는 2007년 사이냅소프트 퀴즈 도입 문제

 

MAX = 99987654321
ans = 0
fibo = [0, 1]
while fibo[-1] <= MAX:
    if fibo[-1] >= 12345678999:
        ans += fibo[-1]
    if fibo[-1] > MAX: break
    fibo.append(fibo[-1] + fibo[-2])
print(ans)
Comments