[백준] 1003 피보나치 함수 - DP(Dynamic Programming, 동적계획법) JAVA

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

 

코드설명

DP 문제입니다.

 

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의 호출 횟수

문제에서 가장 핵심로직은,

dp[N][0] = dp[N-1][0] + dp[N-2][0];

dp[N][1] = dp[N-1][1] + dp[N-2][0]; 

위의 로직을 이해해야합니다.

 

예시를 들면,

피보나치 수 3이 들어왔다고 가정하였을때,

fibo(3) = fibonacci(3-1) + fibonacci(3-2) = fibo(2) + fibo(1) = fibo(1) + fibo(0) + fibo(1) 이 되므로써

fibo(0)은 곧 0이 1번 나오고, fibo(1) 은 1이 2번나온다는 것을 의미합니다. ( 피보나치에서 기본적으로 fibo(0)은 0을 return하고, fibo(1)은 1을 return 합니다. 문제에서 주어진 함수가 있습니다. )

 

 

 

코드

처음에 시간초과 난 코드입니다.

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

public class Main {
    public static int T, N, zeroCnt, firstCnt;
    public static int[] cache;
    public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
        T = Integer.parseInt(st.nextToken());
        cache = new int[41];
        Arrays.fill(cache, -1);
        for(int i=0;i<T; i++) {
        	st = new StringTokenizer(br.readLine());
        	N = Integer.parseInt(st.nextToken());
        	zeroCnt = 0; firstCnt = 0;
        	fibonacci(N);
        	System.out.println(zeroCnt+" "+firstCnt);
        }
        
    }
    
    public static int fibonacci(int n) {
    	if(n == 0) {
    		zeroCnt += 1;
    		return 0;
    	}
    	if(n == 1) {
    		firstCnt += 1;
    		return 1;
    	}
    	int ret = 0;
    	ret = fibonacci(n - 1) + fibonacci(n - 2);
    	return ret;
    }

}

정답코드입니다.

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

public class Main {
	public static int T, N;
	public static int answer = 0;
	public static int[][] dp;
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	
    	T = Integer.parseInt(st.nextToken());
    	dp = new int[41][2];
    	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의 호출 횟수
    	
    	for(int i=2;i<=40;i++) {
    		dp[i][0] = dp[i-1][0] + dp[i-2][0];
    		dp[i][1] = dp[i-1][1] + dp[i-2][1];
    	}
    	
    	for(int i=0;i<T;i++) {
    		st = new StringTokenizer(br.readLine());
    		int a = Integer.parseInt(st.nextToken());
    		System.out.println(dp[a][0] + " "+dp[a][1]);
    	}
    	
    }
    
}

 

Bottom-Up 방식이 아닌, 만약에 Top-Down 방식으로 할 경우입니다.

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

public class Main {
    public static int T, N, zeroCnt, firstCnt;
    public static int[] cache;
    public static int[][] zeroOneCache;
    public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
        T = Integer.parseInt(st.nextToken());
        cache = new int[41];
        zeroOneCache = new int[41][2];
        
        zeroOneCache[0][0] = 1;
        zeroOneCache[0][1] = 0;
        zeroOneCache[1][0] = 0;
        zeroOneCache[1][1] = 1;
        
        for(int i=2; i<41; i++) {
        	Arrays.fill(zeroOneCache[i], -1);
        }
        
        for(int i=0;i<T; i++) {
        	st = new StringTokenizer(br.readLine());
        	N = Integer.parseInt(st.nextToken());
        	int[] answer = fibonacci(N);
        	System.out.println(answer[0] + " "+answer[1]);
        }
        
    }
    
    public static int[] fibonacci(int n) {
    	if(zeroOneCache[n][0] != -1 || zeroOneCache[n][1] != -1) {
    		return zeroOneCache[n];
    	}
    	int[] result1 = fibonacci(n - 1);
    	int[] result2 = fibonacci(n - 2);
    	
    	zeroOneCache[n][0] = result1[0] + result2[0];
    	zeroOneCache[n][1] = result1[1] + result2[1];
    	return zeroOneCache[n];
    }

}