[CLASS 3: DP] 백준 1003 피보나치 함수

1003번: 피보나치 함수

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

 

# 코드

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int t = Integer.parseInt(br.readLine());

        // 미리 피보나치 수를 저장
        int[] fibo = new int[41];
        fibo[0] = 0;
        fibo[1] = 1;
        for (int i = 2; i <= 40; i++) {
            fibo[i] = fibo[i-1] + fibo[i-2];
        }

        for (int j = 0; j < t; j++) {
            int n = Integer.parseInt(br.readLine());
            if (n == 0) {
                sb.append("1 0").append("\n");
            } else if (n == 1) {
                sb.append("0 1").append("\n");
            } else {
                sb.append(fibo[n-1] + " " + fibo[n]).append("\n");
            }
        }
        System.out.print(sb);
        br.close();
    }
}

• 주어진 C++함수 소스와 같이 재귀로 구현하면 바로 시간초과를 받는 문제이다.
• 간단하게 배열에 미리 피보나치 수를 저장해놓은 뒤, 0을 호출하는 수는 바로 직전 피보나치 수라는 점을 이용해 풀었다.

 

문제의 취지에 맞도록 다이나믹 프로그래밍으로 코드를 작성하면 이러할 것이다.

import java.io.*;

public class Main {
    static Integer[][] dp = new Integer[41][2];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int t = Integer.parseInt(br.readLine());

        dp[0][0] = 1;	// n=0 일 때의 0 호출 횟수
        dp[0][1] = 0;	// n=0 일 때의 1 호출 횟수
        dp[1][0] = 0;	// n=1 일 때의 0 호출 횟수
        dp[1][1] = 1;	// n=1 일 때의 1 호출 횟수

        while(t --> 0){
            int n = Integer.parseInt(br.readLine());
            fibonacci(n);
            sb.append(dp[n][0] + " " + dp[n][1]).append('\n');
        }
        System.out.println(sb);
    }

    static Integer[] fibonacci(int n) {
        // n에 대한 0, 1의 호출 횟수가 없을 때 (=탐색하지 않은 값일 때)
        if(dp[n][0] == null || dp[n][1] == null) {
            // 각 N에 대한 0 호출 횟수와 1 호출 횟수를 재귀호출한다.
            dp[n][0] = fibonacci(n - 1)[0] + fibonacci(n - 2)[0];
            dp[n][1] = fibonacci(n - 1)[1] + fibonacci(n - 2)[1];
        }
        // n에 대한 0과 1, 즉 [n][0]과 [n][1] 을 담고있는 [n]을 반환한다.
        return dp[n];
    }
}

 

 

 

DP 코드는 아래 블로그를 참고했다.

[백준] 1003번 : 피보나치 함수 - JAVA [자바]