1003번

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

1003번: 피보나치 함수

유튜브에서 DP관련 영상을 본김에 DP문제를 풀어보기로 했다.

위의 문제는 주어진 코드로 피보나치 함수를 구형하면 시간초과가 난다. 그래서 이것은 중복적으로 계산하는 횟수를 생략하여 DP배열에 저장하고, 그 값을 이용하는 것이다.

즉, 피보나치 수열은 fibonacci(3)=fibonacci(2)+fibonacci(1)이고, fibonacci(4)=fibonacci(3)+fibonacci(2)이니까 이전의 값을 저장해두면 다시 반복해서 계산하는 과정을 생략하고, 값을 구할 수 있다.

즉, fibonacci(4)=fibonacci(3)+dp[fibonacci(2)로 구한 값]이 된다.

여기서는 0과 1의 출력횟수를 세는 것이기 때문에

나는 이걸 2차원 배열을 사용하는 대신 두번 해줬다. 물론 이게 더 비효율적이다...2차원 배열로 했을때 정리를 못해서 이렇게한 것...

다른 이들은 2차원 배열로 한 경우가 있다.

 

1차원 배열 2개를 사용한 나의 풀이에 사용한 객체 클래스는 아래와 같다.

class table{
    int[] dpZero;
    int[] dpOne;

    public table(int n){
        dpZero = new int[n+1];
        dpOne = new int[n+1];
    }
    public int fibonacci(int n){
        if(n==0){
            dpOne[n]=0;
            return dpOne[n];
        }
        else if(n==1){
            dpOne[n]=1;
           return dpOne[n];
        }else
            return dpOne[n]=fibonacci(n-1)+dpOne[n-2];
    }
    public int fibonacciZero(int n){
        if(n==0){
            dpZero[n]=1;
            return 1;
        } else if (n==1) {
            dpZero[n]=0;
            return 1;
        } else
            return dpZero[n]=fibonacciZero(n-1)+dpZero[n-2];
    }
}

위의 클래스를 이용해서 fibonacci와 fibonacciZero를 이용해서 답을 구해냈다.

정답 코드는 아래와 같다.

package backjoon.b1003;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

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

        for(int i=0; i<n; i++){
            int k = Integer.parseInt(br.readLine());
            table t = new table(k);
            t.fibonacci(k);
            t.fibonacciZero(k);
            sb.append(t.dpZero[k]).append(" ").append(t.dpOne[k]).append("\n");
        }
        System.out.println(sb);
    }

}
class table{
    int[] dpZero;
    int[] dpOne;

    public table(int n){
        dpZero = new int[n+1];
        dpOne = new int[n+1];
    }
    public int fibonacci(int n){
        if(n==0){
            dpOne[n]=0;
            return dpOne[n];
        }
        else if(n==1){
            dpOne[n]=1;
           return dpOne[n];
        }else
            return dpOne[n]=fibonacci(n-1)+dpOne[n-2];
    }
    public int fibonacciZero(int n){
        if(n==0){
            dpZero[n]=1;
            return 1;
        } else if (n==1) {
            dpZero[n]=0;
            return 1;
        } else
            return dpZero[n]=fibonacciZero(n-1)+dpZero[n-2];
    }
}

내가 한 방법 외에도 2차원 배열이나 반복문만을 사용해서 푼 경우도 있다.

반복문 원리를 간단히 설명하면 규칙성을 찾은 것이다. bottom-up방법이라고도 한다.(위처럼 재귀함수를 이용하는 경우를top-down)

그래서 반복문으로 하면 이전 값의 1의 출력개수가 현재 값의 0의 출력 개수가 되고, 현재의 1의 출력횟수는 이전 값의 0과 1의 출력횟수의 합이다.

즉, 0 은 1 0, 1은 0 1, 2는 1 1, 3은 1 2, 4는 2 3, ... 이렇듯 4의 경우 3의 1출력횟수인 2가 0의 출력횟수가 되고 1의 출력횟수는 3의 0,1의 출력횟수 합 1+2=3이된다.

5의 0 출력횟수 = 4의 1 출력횟수 = 3

5의 1 출력횟수 = 4의 0 출력횟수 + 4의 1 출력횟수 = 2+3

이렇게 규칙성을 찾는 방법도 있다.