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

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

 

[문제 이해]

피보나치는 어떻게 구현하는지 알고 있어서 쉽게 재귀로 구현하고 끝내려고 했으나 실버 3인 이유가 있었구나.. 그냥 재귀 함수로 0과 1의 개수를 구하는 전역 변수를 사용하는 것이 아니라 dp를 사용하여 시간초과가 나지 않도록 구현하는 것이 중요한 문제였다. 

 

[문제 풀이]

처음 풀었을 때는

import java.io.*;
import java.sql.Array;
import java.util.*;

public class Main {

    public static int sum_zero = 0;
    public static int sum_one = 0;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());
        for(int i = 0; i < n; i++){
            BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

            fibo(Integer.parseInt(br.readLine()));

            bw.write(String.valueOf(sum_zero) + " " + String.valueOf(sum_one)+"\n");
            bw.flush();
            sum_zero = 0;
            sum_one = 0;
        }
    }

    public static int fibo(int n){
        if(n == 0){
            sum_zero++;
            return sum_zero;
        }
        else if(n == 1){
            sum_one++;
            return sum_one;
        }
        else{
            return fibo(n-1) + fibo(n-2);
        }
    }
}

 

sum_zero와 sum_one이라는 전역 변수를 사용했었는데 이렇게 하면 시간 초과가 뜬다. 에라이~

dp를 사용해서 풀어보자. 일단 0의 경우, 0을 리턴하지만 1은 리턴하지 않고, 1의 경우는 1을 리턴하지만 0을 리턴하지는 않는다. 이걸 쭉 나타내보면 아래와 같은데..

n	0 호출 횟수	1 호출 횟수
0	1	0
1	0	1
2	1	1
3	1	2
4	2	3
5	3	5
6	5	8

 

위의 표에서도 알 수 있듯이 규칙이 있다. 0 호출 횟수도 피보나치 함수에 맞게 n>1부터는 n-1이랑 n-2의 0 호출 횟수를 더한 것과 동일하고 1의 경우도 마찬가지이다. 이 규칙에 따라 dp 2차원 배열에 초반 0과 1까지만 직접 지정해주고 나머지는 규칙에 따라 값을 세팅할 수 있게 함수를 구현하면 끝이다!!!!

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));

        dp[0][0] = 1; // 0일 때 0 호출 횟수 = 1번
        dp[0][1] = 0; // 0일 때 1 호출 횟수 = 0번
        dp[1][0] = 0; // 1일 때 0 호출 횟수 = 0번
        dp[1][1] = 1; // 0일 때 1 호출 횟수 = 1번
        int n = Integer.parseInt(br.readLine());
        for(int i = 0; i < n; i++){
            BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

            int m = Integer.parseInt(br.readLine());
            fibo(m);

            bw.write(String.valueOf(dp[m][0]) + " " + String.valueOf(dp[m][1])+"\n");
            bw.flush();
        }
    }


    public static Integer[] fibo(int n){
        if(dp[n][0] == null || dp[n][1] == null){
            dp[n][0] = fibo(n-1)[0] + fibo(n-2)[0];
            dp[n][1] = fibo(n-1)[1] + fibo(n-2)[1];
        }
        return dp[n];
    }
}