[백준 / Java] 1003번: 피보나치 함수 (DP)

코테99 21일차 문제는 백준 1003번 '피보나치 함수'다.

 

---

 문제 이해

이 문제는 피보나치 함수의 재귀 호출 과정에서 0과 1이 몇 번 출력되는지를 계산하는 문제다. 일반적인 피보나치 수열을 구하는 방식이 아니라, 특정 값이 반환될 때마다 몇 번 호출되는지를 파악해야 한다.

예를 들어, fibonacci(3)을 호출하면 다음과 같은 과정이 진행된다:

fibonacci(3) -> fibonacci(2) + fibonacci(1)
fibonacci(2) -> fibonacci(1) + fibonacci(0)
fibonacci(1) = 1 (출력: 1)
fibonacci(0) = 0 (출력: 0)
fibonacci(2) 결과 = 1 (출력: 1)
fibonacci(3) 결과 = 2 (출력: 1)

위 과정에서 0은 1번, 1은 2번 출력된다.

이처럼 N값에 따라 0과 1이 호출되는 횟수를 빠르게 계산하는 방법을 찾아야 한다.

---

접근 방법

1. 초기 접근 (재귀 사용)

• 피보나치 함수를 그대로 재귀 호출하면 중복 연산이 너무 많아진다.
• fibonacci(40)을 단순 재귀로 구현하면 약 10억 번 이상 호출될 수 있어 시간 초과가 발생한다.

2. 변경된 접근 (DP 활용)

• 피보나치 수열의 특성을 이용해 0과 1이 출력되는 횟수도 피보나치 형태로 증가함을 이용한다.
• 즉, count0[n]과 count1[n]은 다음과 같은 점화식을 따른다:
  • count0[n] = count0[n-1] + count0[n-2]
  • count1[n] = count1[n-1] + count1[n-2]
• 이를 이용해 Dynamic Programming (DP) 방식으로 미리 값을 계산해두면, 각 테스트 케이스에서 O(1)의 시간 복잡도로 답을 구할 수 있다.

---

알고리즘 진행 순서

1. 배열을 선언하여 DP 테이블을 저장 (dp[41][2] → 최대 N이 40이므로 41까지 선언)
2. 기본 값 설정
   • dp[0][0] = 1, dp[0][1] = 0 (fibonacci(0) → 0이 1번, 1이 0번 출력)
   • dp[1][0] = 0, dp[1][1] = 1 (fibonacci(1) → 0이 0번, 1이 1번 출력)
3. 점화식을 활용해 DP 테이블을 채움 (N=2부터 N=40까지 반복)
   • dp[n][0] = dp[n-1][0] + dp[n-2][0]
   • dp[n][1] = dp[n-1][1] + dp[n-2][1]
4. 각 테스트 케이스에서 dp[N][0]과 dp[N][1]을 출력

---

구현 코드

package Boj;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Boj1003 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int T = Integer.parseInt(br.readLine());

        int[][] dp = new int[41][2];

        // 초기값 설정
        dp[0][0] = 1;
        dp[0][1] = 0;

        dp[1][0] = 0;
        dp[1][1] = 1;

        for (int i = 2; i <= 40; i++) {
            dp[i][0] = dp[i - 1][0] + dp[i - 2][0];
            dp[i][1] = dp[i - 1][1] + dp[i - 2][1];
        }

        for (int t = 0; t < T; t++) {
            int N = Integer.parseInt(br.readLine());
            sb.append(dp[N][0]).append(" ").append(dp[N][1]).append("\n");
        }

        System.out.print(sb);
    }
}

 

---

회고

• 단순한 재귀 구현이 항상 좋은 것은 아니다. 중복 연산이 많을 경우 DP를 고려해야 한다.
• 문제에서 "큰 값을 입력으로 받아도 효율적으로 해결해야 한다"는 점을 유의해야 한다.
• 피보나치 수열은 DP로 해결하는 것이 가장 효율적이다.
• 출력 속도를 고려해 StringBuilder를 사용하는 것이 좋다.

추가 최적화 가능성

• dp 배열을 전역 변수로 선언하면 main() 내에서 매번 배열을 생성할 필요 없이 최적화 가능하다.
• 배열 없이 변수 2개만 사용해도 해결할 수 있다. (공간 복잡도 O(1))