[BOJ] 백준 1003 피보나치 함수

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

 Input 
3
0
1
3　 

 Output 

1 0
0 1
1 2

재귀를 이용하는 경우 시간 초과나기 때문에 반복문을 이용하여 구현

 

[수학] 피보나치 수열 구현 (재귀, DP)

[문제 풀이]

(0호출, 1호출)을 분석해보면

N=0 일 때, (1, 0) / N=1 일 때, (0, 1)까지를 기본(base)항으로 둔다.

다음항부터 (1, 1) → (1, 2) → (2, 3) → (3, 5) → ( X[n-1] + X[n-2], Y[n-1] + Y[n-2] ) 점화식 이용.

---

import java.util.Scanner;
 
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
         
        int T = Integer.parseInt(sc.nextLine());
         
        int[][] result = new int[41][2];
 
    // 기본항 설정
        result[0][0] = 1; result[0][1] = 0;
        result[1][0] = 0; result[1][1] = 1;
 
    // Dynamic
        for(int x=2; x<41; x++) {
            for(int y=0; y<=1; y++) {
                result[x][y] = result[x-1][y] + result[x-2][y];
            }
        }
         
        // Test Case
        int[] n = new int[T];
        for(int i=0; i<T; i++) {
            n[i] = Integer.parseInt(sc.nextLine());
        }
         
        // solution 출력      
        for(int i=0; i < T; i++) {
            System.out.println( result[n[i]][0]+ " " + result[n[i]][1] );
        }  
    }
}