[Algorithm/Java] 백준 1003번 - 피보나치 함수

---

https://www.acmicpc.net/problem/1003

---

📌 문제

문제 유형

• DP

문제 설명

재귀로 구현된 피보나치 함수 fibonacci(n)이 0과 1을 각각 몇 번 출력하는지 구하는 문제

1은 2번 출력되고, 0은 1번 출력된다. N이 주어졌을 때, fibonacci(N)을 호출했을 때, 0과 1이 각각 몇 번 출력되는지 구하는 프로그램을 작성하시오.

입출력 예시

입력

3
0
1
3

출력

각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다.

1 0
0 1
1 2

🔍 문제 풀이

DP란?

다이나믹 프로그래밍(DP)이란?

• 큰 문제를 작은 문제로 나눠서 푸는 알고리즘 설계 기법
• 이미 푼 문제의 정답을 저장해두고, 중복 계산을 피하는 방식이다.
• 재귀로 풀면 같은 계산을 반복하게 되어 비효율적인데, 이 문제를 DP로 풀면 방식으로 0과 1이 각각 몇 번 출력되는지 미리 계산해두어 속도를 비약적으로 줄일 수 있다.

fibonacci(n) = fibonacci(n - 1) + fibonacci(n - 2) // 피보나치 함수 점화식 (재귀)

풀이 과정

① DP 배열 크기 정하기

문제에서 n ≤ 40이므로 dp[41][2]로 선언

• dp[n][0]: fibonacci(n) 호출 시 0 출력 횟수
• dp[n][1]: fibonacci(n) 호출 시 1 출력 횟수

② DP 배열 초기값 세팅 (dp[0], dp[1])

dp[0]과 dp[1]은 점화식 계산을 시작하기 위한 필수 초기값이기 때문에 먼저 채운다.

dp[0][0] = 1; // fibonacci(0) → 0 출력 1회
dp[0][1] = 0;

dp[1][0] = 0;
dp[1][1] = 1; // fibonacci(1) → 1 출력 1회

이렇게, 맨 처음 두 행만 직접 채우고, 나머지는 점화식으로 자동 계산한다.

n	dp[n][0] (0 출력 횟수)	dp[n][1] (1 출력 횟수)
0	1	0
1	0	1
2	0	0
3	0	0
4	0	0
…	…	…
40	0	0

③ DP채우기(점화식)

• 최대 n은 40이므로, 미리 0~40까지 DP 배열을 채운다.
• fib(n)은 fib(n-1) + fib(n-2)이므로, 출력 횟수도 이전 두 값을 더하면 된다.

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];
}

n	fibonacci(n) 호출 시	dp[n][0] (0 출력 횟수)	dp[n][1] (1 출력 횟수)
0	fibonacci(0)	1	0
1	fibonacci(1)	0	1
2	fibonacci(1) + fibonacci(0)	1 (0+1)	1 (1+0)
3	fibonacci(2) + fibonacci(1)	1 (1+0)	2 (1+1)
4	fibonacci(3) + fibonacci(2)	2 (1+1)	3 (2+1)
…	…	…	…

④ 이후 각 테스트케이스에서 dp[n][0], dp[n][1] 을 출력

💭 배운 점

배운 점 1)

문제에서 중복 호출이 많은 재귀 함수는 DP로 최적화할 수 있다.

배운 점 2)

점화식을 통해 반복적으로 값을 채워나가는 구조가 DP의 핵심이다.

그래서 배열을 선언하고, 작은 문제부터 차례대로 누적 계산해가는 방식이 많다.

💻 전체 코드

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // dp[i][0] = fib(i) 호출 시 0이 출력되는 횟수
        // dp[i][1] = fib(i) 호출 시 1이 출력되는 횟수
        int[][] dp = new int[41][2];

        // 초기값: 직접 채움 (맨 위 2행)
        dp[0][0] = 1; // fibonacci(0) → 0 출력
        dp[0][1] = 0;

        dp[1][0] = 0;
        dp[1][1] = 1; // fibonacci(1) → 1 출력

        // 점화식으로 DP 채우기(나머지 행)
        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];
        }

        // 테스트 케이스 처리
        int t = Integer.parseInt(br.readLine());

        for (int i = 0; i < t; i++) {
            int n = Integer.parseInt(br.readLine());
            System.out.println(dp[n][0] + " " + dp[n][1]);
        }

    }
}