[알고리즘][백준][JAVA] 1003번 : 피보나치 함수 / 다이나믹 프로그래밍

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

1003번: 피보나치 함수

해당 문제는 피보나치 수열 중 하나를 호출하는 데에 필요한 피보나치(0) 과 피보나치 (1) 함수의 호출횟수를 카운트하는 문제이다.

이러한 문제는 전에 풀어본 유형인 다이나믹 프로그래밍으로, 5까지만 호출횟수를 세어도 DP 유형임을 파악할 수 있다.

 

다이나믹 프로그래밍에 관한 포스팅은 이전 포스팅인 "9095번 : 1,2,3 더하기 " 문제에서 자세히 다루었으니 참고하면 된다.

https://codingjust.tistory.com/21

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 T = Integer.parseInt(br.readLine());        // 테스트 케이스의 개수

        int fibo [][] = new int[41][41];    // 0과 1의 호출횟수를 저장할 2차원배열 선언

        // 초기값 설정
        fibo[0][0]=1;       //0일때 0 호출횟수 : 1
        fibo[0][1]=0;       //0일때 1 호출횟수 : 0
        fibo[1][0]=0;       //1일때 0 호출횟수 : 0
        fibo[1][1]=1;       //1일때 1 호출횟수 : 1

        // fibo 배열 안의 값 채우기
        for (int i=2;i<41;i++){
            fibo[i][0]=fibo[i-1][0]+fibo[i-2][0];   // 0 호출횟수에 대한 점화식
            fibo[i][1]=fibo[i-1][1]+fibo[i-2][1];   // 0 호출횟수에 대한 점화식
        }

        for (int i=0;i<T;i++){
            int N = Integer.parseInt(br.readLine());
            System.out.printf("%d %d\n" ,fibo[N][0], fibo[N][1]);
        }
    }
}