박시은

(❁´◡`❁)

2 분 소요


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][0] fibonacci(n)을 실행했을 때 fibonacci(0)이 호출된 횟수
dp[n][1] fibonacci(n)을 실행했을 때 fibonacci(1)이 호출된 횟수


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

    }
}


카테고리:

업데이트:

댓글남기기

참고