프로젝트 오일러 02번 문제_피보나치 수열

문제 1.

피보나치 수열에서 4백만 이하이면서 짝수인 항의 합

출처 : https://euler.synap.co.kr/problem=2

• 피보나치(Fibonacci) 수열의 각 항은 바로 앞의 항 두 개를 더한 것이다. 1과 2로 시작하는 경우 이 수열은 아래와 같다.

  1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

  4백만 이하의 짝수 값을 갖는 모든 피보나치 항을 더하면 얼마가 될까?

 

문제 풀이

fiboSum = 2

fibo_1 = 1
fibo_2 = 2
fibo_3 = 0

while(True):
    if(fibo_3 > 4000000):
        break

    fibo_3 = fibo_1 + fibo_2
    print("fibo_3", fibo_3)

    if(fibo_3 % 2 == 0):
        fiboSum += fibo_3

    fibo_1 = fibo_2
    fibo_2 = fibo_3


print("fiboSum", fiboSum)

 

 

문제를 풀기 전에 왼쪽처럼 피보나치 수열을 나열해놓고서 규칙성을 찾아 보았다.

처음 1, 2가 합쳐진 결과 An+2(an+2로 표기해놨지만 키보드로 표현할 수가 없으니..) 는 3, 5, 8, 13, 21 이 됨을 볼 수 있다.

이러한 An+2는 그 다음에 An+2, An이 됨을 볼 수 있다. 이러한 규칙성을 파악하여 오른쪽과 같은 코드를 세워보았다. 

 

따라서 정답은 4613732