[BOJ 1003] 피보나치 함수 (Java, DP)

 

 

---

문제 링크

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

1003번: 피보나치 함수

---

문제 풀이

- 매 테스트 케이스마다 피보나치 함수로 구할 경우 '시간 초과' 에러 발생

- fibo(N) = fibo(N - 1) + fibo(N - 2) 형태로 구해지는 피보나치 수열은 재귀 방식으로 구할 때 O(2^n) 시간복잡도 가짐 

(N이 최대 40일 때 2^40은 대략 10^12)

 

그래서

- 상향식으로 40번째 배열 까지 DP 배열에 값을 구한 후 호출하게 되면 O(N) 시간복잡도로 구해짐 

 

이때 0, 1 초기항 처리 후 호출

0	1	2	3	4	5
0	1	1	2	3	4

 

특이한 게 fibo(N)에 대한 0과 1의 카운트는 아래와 같이 구해진다

사용된 0 카운트	사용된 1 카운트
fibo(N - 1)	fibo(N)

---

제출 코드

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

public class Main {

    static StringBuilder sb = new StringBuilder();

    static int T, N;

    static int[] DP;
    static void input() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        T = Integer.parseInt(br.readLine());

        while(T > 0) {
            T -= 1;

            N = Integer.parseInt(br.readLine());
            
            if(N == 0) sb.append(1).append(" ").append(0).append("\n");
            else sb.append(DP[N - 1]).append(" ").append(DP[N]).append("\n");
        }
    }

    static void fibonacci() {
        DP = new int[41];
        DP[0] = 0;
        DP[1] = 1;
        for(int i = 2; i <= 40; i++) {
            DP[i] = DP[i - 1] + DP[i - 2];
        }
    }

    public static void main(String[] args) throws Exception {
        fibonacci();
        input();
        System.out.println(sb);
    }
    
}

 

 

참고. 

https://www.acmicpc.net/blog/view/28

피보나치 수를 구하는 여러가지 방법