[Project Euler #2][C++] 피보나치 수열에서 4백만 이하이면서 짝수인 항의 합

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

문제

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

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

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

문제 해결 방법

• 문제의 조건을 잘 확인해야 한다.
  • 4백만 이하의 짝수 값 을 갖는 모든 피보나치 항을 더하라.
    • 즉, 피보나치 항의 값이 4백만 이하인 수 중에서 짝수 값을 갖는 모든 피보나치 항을 더하는 문제이다.
    • 나는 문제를 잘못 이해해서 연산을 4백만 번 수행 하는 작업을 반복하였고, 계속 오답 처리가 되어 멘탈이 붕괴되는 상황을 맞닥드리게 되었다.
      • 문제 번역자가 변역을 깔끔하게 하지 못해서 생긴 문제였다.
• 반복 연산을 수행하면서, 2로 나누어 떨어지는 피보나치의 항들의 축적합(sum)을 구하면 간단하게 해결되는 문제이다.
• 여기서 피보나치 항을 구하는 알고리즘을 파악해 둘 필요가 있었다.

int value1 = 1, value2 = 2;

// UPDATE
int tmp = value2;
value2 += value1;  // value2 <- value1 + value2, 
value1 = tmp;      // value1 <- 업데이트 되기 전의 value2의 값

소스 코드

#include <iostream>
using namespace std;
 
#define MAX_NUM 4000000
 
int main() {
    int value1 = 1, value2 = 2, sum = 0;
 
    while (1) {
        if (value2 <= MAX_NUM) {  // 4백만 이하                                                                                
            if (value2 % 2 == 0) {
                sum += value2;
            }
            // UPDATE
            int tmp = value2;
            value2 += value1;
            value1 = tmp;
        }
        else {
            break;
        }
    }
 
    cout << sum << endl;
 
    return 0;
}

정답

4613732

심화 공부

피보나치 수(Fibonacci Numbers)

피보나치 수 $F_{n}$ 은 다음과 같은 초기값 및 점화식으로 정의되는 수열이다.

$F_{0} = 0, F_{1} = 1, F_{n} = F_{n-1} + F_{n-2} (n \in {2, 3, 4, ...})$

피보나치 수의 처음 몇 항은 (0번째 항부터 시작할 경우) 다음과 같다.

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, ...

피보나치 수의 일반항은 다음과 같다.

$F_{n} = \frac{\varphi^{n} - (1 - \varphi)^{n}}{\sqrt{5}} = \frac{1}{\sqrt{5}}\begin{pmatrix} \begin{pmatrix} \frac{1 + \sqrt{5}}{2} \end{pmatrix}^{n} - \begin{pmatrix} \frac{1 - \sqrt{5}}{2} \end{pmatrix}^{n}  \end{pmatrix} = \frac{(1 + \sqrt{5})^{n} - (1 - \sqrt{5})^{n}}{2^{n}\sqrt{5}}$

- 여기서 $\varphi$ 는 황금비 이며, $\sqrt{5}$ 는 5의 제곱근이다.

- 이를 비네 공식(Binet's Formula) 이라고 한다.

- 이는 레온하르트 오일러 가 1765년 처음 발표했으나, 잊혀졌다가 1948년 자크 비네 에 의해 재발견되었다.

---

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