[Java] 1003번: 피보나치 함수 Silver 3

문제 링크

실버 3 DP 문제는 다 똑같은 것 같다..

이 문제도 이전 문제들과 껍데기만 달랐지, 풀이 방식은 똑같았다.

근데 문제에서 과정까지 설명해줬다보니 더욱 수월하게 풀렸다.

X[3] 은 X[3-1]과 X[3-2]를 호출하기 때문에 이전과 그전의 합을 계속 누적합한다.

그래서 점화식은 이렇게 된다.

X[N] = X[N-1] + X[N-2]

정답

import java.io.*;
import java.util.*;

public class Main {

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

        // T 입력 받기
        int T = Integer.parseInt(br.readLine());

        // DP 배열 생성
        int[][] dp = new int[41][2];
        dp[0][0] = 1;
        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];
        }

        // 테스트 케이스 입력 받기
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < T; i++) {
            int N = Integer.parseInt(br.readLine());
            sb.append(dp[N][0]).append(" ").append(dp[N][1]).append("\n");
        }

        // 출력
        System.out.println(sb);
    }
}