DP - 백준1003 피보나치 함수

그냥 피보나치 수를 구하는 것이 아니라, 주어진 수를 구할 때 피보나치 재귀함수에서 boundary contion에서 n이 0인 경우와 1인 경우 각각 몇 번씩인지 구하는 문제이다.

일단 직접 재귀함수를 돌려보면서 카운트해보니 시간초과가 나왔다.
그래서 각 수에서 0과 1을 구하기 위해 어떻게 메모이제이션을 이용할 수 있을지 고민해보았다. 쉽게 떠오르지 않았는데, 역시 직접 그리면서 테이블을 채워보니 바로 알게 되었다.

코드 주석 참고

import java.util.*;
import java.io.*;
public class Main{
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());
        //dp테이블 생성
        int[][] dp = new int[41][2];
        //점화식
        //n = n-1 + n-2
        //dp[n][0] = dp[n-1][0] + dp[n-2][0]
        //dp[n][1] = dp[n-1][1] + dp[n-2][1]
        //초기값 세팅
        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 i = 0; i < t; i++){
            int n = Integer.parseInt(br.readLine());
            System.out.println(dp[n][0] + " " + dp[n][1]);
        }
    }
}