프로젝트 오일러 :: 02번 문제풀이 :: java

문제

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

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

짝수이면서 4백만 이하인 모든 항을 더하면 얼마가 됩니까?

풀이

피보나치 수열의 규칙은 다음과 같다.

• 처음 항은 1이다.
• 두번째 항은 2이다.
• 1과 2를 제외한 n번째 항은 (n-1번째 항)+(n-2번째 항) 이다.

위 규칙을 기반으로 피보나치 수열을 구하는 알고리즘은 다음과 같이 표현할 수 있다.

while(true) {

       fiboIdx_03 = fiboIdx_01 + fiboIdx_02;

       fiboIdx_01 = fiboIdx_02;

       fiboIdx_02 = fiboIdx_03;

}

아래와 같이 위 알고리즘에 짝수이면서 4백만 이하의 항의 합을 구하는 조건만 추가해주면 답을 구할 수 있다.

public class Problem_02 {

       public void solution() {

              int fiboIdx_01, fiboIdx_02, fiboIdx_03, sum;

              fiboIdx_01 = 1;

              fiboIdx_02 = 1;

              sum = 0;

              while (true) {

                     fiboIdx_03 = fiboIdx_01 + fiboIdx_02;

                     /* 4백만 이상일 경우 루프 탈출 */

                     if (fiboIdx_03 > 4000000)

                           break;

                     /* 짝수인 경우에만 sum에 더해줌 */

                     if (fiboIdx_03 % 2 == 0)

                           sum += fiboIdx_03;

                     fiboIdx_01 = fiboIdx_02;

                     fiboIdx_02 = fiboIdx_03;

              }

              System.out.println("" + sum);

       }

}

결과는 아래와 같으며 문제의 정답이다.

~ Epilogue ~

이번 문제의 핵심은 피보나치 수열을 구하는 알고리즘을 구현할 수 있는가이다. 한 문제 한 문제 풀어가며 내 머리가 이해하는 로직을 컴퓨터가 이해하는 코드로 구현할 수 있도록 하자.

github