백준 - 1003번(피보나치 함수)

문제 출처: https://www.acmicpc.net/problem/1003

문제

• fibonacci(3)을 호출하면 다음과 같은 일이 일어난다.

  • fibonacci(3)은 fibonacci(2)와 fibonacci(1) (첫 번째 호출)을 호출한다.
  • fibonacci(2)는 fibonacci(1) (두 번째 호출)과 fibonacci(0)을 호출한다.
  • 두 번째 호출한 fibonacci(1)은 1을 출력하고 1을 리턴한다.
  • fibonacci(0)은 0을 출력하고, 0을 리턴한다.
  • fibonacci(2)는 fibonacci(1)과 fibonacci(0)의 결과를 얻고, 1을 리턴한다.
  • 첫 번째 호출한 fibonacci(1)은 1을 출력하고, 1을 리턴한다.
  • fibonacci(3)은 fibonacci(2)와 fibonacci(1)의 결과를 얻고, 2를 리턴한다.
  • 1은 2번 출력되고, 0은 1번 출력된다. N이 주어졌을 때, fibonacci(N)을 호출했을 때, 0과 1이 각각 몇 번 출력되는지 구하는 프로그램을 작성하시오.

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

public class Main {

    private static int countZero, countOne;

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

        while (T-- > 0) {
            int N = Integer.parseInt(reader.readLine());
            int[] fibo = new int[N + 1];
            int[][] counts = new int[N + 1][2];
            countZero = 0;
            countOne = 0;

            fibonacci(counts, fibo, N);
            sb.append(countZero).append(" ").append(countOne).append("\n");
        }

        System.out.println(sb);
    }

    private static int fibonacci(int[][] counts, int[] nums, int n) {
        if (n == 0) {
            counts[n][0] = 1;
            countZero += counts[n][0];
            return 0;
        }

        if (n == 1) {
            counts[n][1] = 1;
            countOne += counts[n][1];
            return 1;
        }

        if (nums[n] != 0) {
            // n == 2부터
            counts[n][0] = counts[n - 1][0] + counts[n - 2][0];
            counts[n][1] = counts[n - 1][1] + counts[n - 2][1];
            countZero += counts[n][0];
            countOne += counts[n][1];
            return nums[n];
        }

        // 이게 메모이제이션!
        nums[n] = fibonacci(counts, nums, n - 1) + fibonacci(counts, nums, n - 2);

        return nums[n];
    }

}

• DP를 활용한 문제를 요즘 연습하고 있는 중에 풀어보게 되었다.
• 처음엔 단순히 0일때와 1일때 변수 카운트를 증가하는 식으로 풀었는데, 문제를 완전히 잘못 이해한 것이었다.
• 각 숫자별로 0과 1의 횟수를 저장할 2차원 배열을 생성한 뒤(counts), 메모이제이션과 함께 값을 누적해가며 푸는 방식으로 해결하였다. 아직 동적 프로그래밍과 재귀 함수가 익숙치 않아 바로바로 나오지는 않지만, 좀 더 연습해서 동적 프로그래밍을 자연스럽게 다룰 수 있도록 노력해야겠다.