0x10 - DP : BOJ1003 피보나치 함

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

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

        // 1. 테이블
        // d[i][2] : fibonacci(i)를 호출했을때 0, 1이 호출되는 횟수
        int[][] d = new int[41][2];

        // 2. 초기값
        d[0][0] = 1; d[0][1] = 0;
        d[1][0] = 0; d[1][1] = 1;
        d[2][0] = 1; d[2][1] = 1;
        d[3][0] = d[2][0]; d[3][1] = d[2][1]+1;

        //3. 점화식
        for (int k = 4; k <= 40; k++) {
            d[k][0] = d[k-1][0] + d[k-2][0];
            d[k][1] = d[k-1][1] + d[k-2][1];
        }

        //4. 출력
        for (int i = 0; i < n; i++) {
            int cur = Integer.parseInt(br.readLine());
            System.out.println(d[cur][0]+" "+d[cur][1]);
        }
    }
}

1. 테이블 설정
   d[i][0] : fibonacci(i)를 호출했을때 0이 호출되는 횟수
   d[i][1] : fibonacci(i)를 호출했을때 1이 호출되는 횟수

2. 초기값 설정
   fibonacci(3) = fibonacci(2) + fibonacci(1) 이므로
   d[3][0]까지 설정해줘야 함

3. 점화식
   그냥 피보나치 그대로 i-1, i-2 더해주면 됨