백준 1003번 피보나치 함수: 0과 1의 출력 횟수 저장하기

함수의 값이 아니라 출력 횟수를 셉니다

피보나치 함수를 그대로 재귀 호출하는 대신, 0과 1이 출력되는 횟수의 규칙을 찾았습니다. 아래 기록에서 앞의 값은 0을, 뒤의 값은 1을 출력한 횟수입니다.

피보나치 함수에서 0과 1의 출력 횟수 규칙을 정리한 원문 그림

dp[n][0]에는 0의 출력 횟수를, dp[n][1]에는 1의 출력 횟수를 저장합니다. n이 0이면 횟수는 (1, 0)이고, 1이면 (0, 1)입니다.

그다음부터는 바로 앞 두 항의 같은 위치를 더합니다. 피보나치 함수가 n - 1과 n - 2를 호출하므로 각각에서 출력한 횟수를 합하면 됩니다. 코드에서는 40까지 미리 계산하고 질문마다 해당 행의 두 값을 출력했습니다.

당시 제출 코드

Java

import java.io.*;

class Main {

    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

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

        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 < 41; 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 i = 0; i < T; i++) {
            int n = Integer.parseInt(br.readLine());
            bw.write(dp[n][0] + " " + dp[n][1]);
            bw.write("\n");
        }
        bw.flush();
    }
}