BOJ] 1003. 피보나치 함수

BOJ]1003. 피보나치 함수

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

DP의 맛보기 문제정도이다.
단순히 피보나치의 결과를 구하는 문제가 아니다.
피보나치 함수가 호출되었을 때, 0과 1이 얼마나 반환(출력)되는지 구하는 문제이다.

규칙을 살펴보자.
예를 들어,
fibo(n) : (0의 반환횟수, 1의 반환횟수) 라고 하자.

fibo(0) : (1,0)
fibo(1) : (0,1)
fibo(2) : (1,1) -> fibo(0) + fibo(1) -> (1,0) + (0,1)
fibo(3) : (1,2) -> fibo(1) + fibo(2) -> (0,1) + (1,1)
fibo(4) : (2,3) -> fibo(2) + fibo(3) -> (1,1) + (1,2)

피보나치의 규칙을 활용하되, 실제 피보나치 값이 아닌 0과 1의 반환 결과를 가지고 계산을 하는 것이다.


문제에서 주어지는 N의 범위는 0이상 40이하이므로, 배열을 41까지 선언해주고 그 값까지의 모든 경우를 구해놓았다.
그리고 나서 결과만 출력해주도록 했다.

public class bj_1003_피보나치함수 {
    static int[][] memo;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
 
        memo = new int[41][2];
        memo[0][0] = 1;
        memo[0][1] = 0;
        
        memo[1][0] = 0;
        memo[1][1] = 1;
        
        for(int i=2; i<41; i++) {
            for(int j=0; j<2; j++) {
                memo[i][j] = memo[i-2][j]+memo[i-1][j];
            }
        }
        
        int T = sc.nextInt();
        for(int tc=1; tc<=T; tc++) {
            int n = sc.nextInt();
            System.out.println(memo[n][0] +" " + memo[n][1]);
        }//end test cases
    }//end main
}