티스토리 뷰



문제

피보나치 수열의 각 항은 바로 앞의 항 두 개를 더한 것이 됩니다. 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 ~

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




댓글