[BOJ] 백준 1003 - 피보나치 함수 (자바)

DP ....,,,,

재귀로 예전에 맞았었는데 재채점 이후 시간초과가 났다.

그래서 DP로 작성했더니 통.과.!

사용된 0과 1의 갯수를 출력하는 문제였기 때문에 나는 0의 배열과 1의 배열을 만들었다.

의 재귀 함수를 DP로 바꾸면 된다. 

풀이

1. 피보나치 값이 0과 1일때는 바로 "1 0", "0 1" 로 출력한다.

2. arr[][] 함수를 만들어서 0과 1을 따로 카운트 한다.

3. 현재값은 전의값과 전전값이 합쳐진 값이기 때문에 아래와 같은 방정식이 나오게 된다.

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

위의 식을 이용하면 끄읏.

소스

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
 
class Main {
 
    static BufferedReader br;
 
    public static void main(String[] args) throws Exception {
 
        //br = new BufferedReader(new InputStreamReader(System.in));
        br = new BufferedReader(new InputStreamReader(new FileInputStream("input.txt")));
        int TestCase = Integer.parseInt(br.readLine());
 
        for (int t = 0; t < TestCase; t++) {
            int n = Integer.parseInt(br.readLine());
            int[][] arr = new int[n+1][2];
            // 0일때
            if(n==0) {
                System.out.println("1 0");
                continue;
            }
            // 1일때
            if(n==1){
                System.out.println("0 1");
                continue;
            }
            arr[0][0] = 1;
            arr[1][1] = 1;
            
            for(int i=2; i<=n; i++){
                arr[i][0] = arr[i-1][0]+arr[i-2][0];
                arr[i][1] = arr[i-1][1]+arr[i-2][1];
                
            }
 
            System.out.println(arr[n][0]+" "+arr[n][1]);
 
        }
    }
}