Project Euler - 문제 2번

Even Fibonacci numbers

Problem 2

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:

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

By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

 문제 2번 : 피보나치 수열에서 각각의 새로운 항은 그 전의 두 항을 더해서 만들어진다. 첫 두 항을 1과 2로 시작해서 첫 10개의 항은 다음과 같다:

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

400만이 넘지 않는 피보나치 수열의 항들을 생각할 때에, 짝수 항들의 합은 얼마인가?

---

 이미 손으로 풀 수 없는 숫자가 나왔습니다. 400만이 넘지 않는 피보나치 수열을 모조리 생각해야 하는데, 이걸 손으로 할 수는 없겠지요. 먼저 피보나치 수열의 정의를 알아야 합니다. 만약 피보나치 수열의 n번째 항을 \(P(n)\)이라고 하면,
$$P(n)=P(n-1)+P(n-2)$$
가 됩니다. 이후에 \(P(n)\)이 400만 이하가 되도록 while문을 주고, 짝수인지를 체크하면서 모두 더하면 될 것 같습니다.

#include <cstdlib>
#include <iostream>
#include "time.h"
using namespace std;

int main()
{
    clock_t start=clock();
  
    int p1=1;
    int p2=1; 
    int sum=0;
    
    while(p2<4000000)
    {
        if(p2%2==0)
           sum=sum+p2;
        int temp=p1; 
        p1=p2;
        p2+=temp;       
    }
    
    clock_t end=clock();
    printf("결과 : %d \n시간 : %lf", sum, end);
    return 0;
}

 이렇게 코드를 짜면, p1은 p2를 내려받고 p2는 기존의 p1과 p2의 합으로 변하면서 p2항이 피보나치 수열을 계속 만들어가게 됩니다. 그 때에, p2가 400만 이하이면서 짝수이면 sum으로 모두 더해서 결과를 출력하도록 하였습니다.

 결과값을 입력해주니 정답이 맞았네요! 앞선 포스트에서 말씀드린 것처럼, 결과는 가리도록 하겠습니다.