[백준] 9095 1, 2, 3 더하기 - DP(동적계획법, Dynamic Programming) JAVA

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

9095번: 1, 2, 3 더하기

코드설명

DP 문제입니다.

 

1, 2, 3 을 각 숫자로 나타내보겠습니다.

 

1을 나타내는경우는

+1 

한가지입니다.

 

2를 나타내는 경우는

+1+1

+2

2가지입니다.

 

3을 나타내는 경우는

1+1+1

+1+2

+2+1

+3

 

4를 나타내는 경우는

1+1+1+1

+1+1+2

+1+2+1

+2+1+1

+1+3

+2+2

+3+1

 

규칙성을 볼 수 있습니다.

4를 나타낸다면, 1을 만들 수 있는 경우의 수에 + 3 , 2를 만들 수 있는경우의 수에 + 2, 3을 만들 수 있는 경우의 수에 +1 씩 하면 각각 모두 4가 만들어질 수 있습니다.

그러몰, dp[4] = dp[1] + dp[2] + dp[3] 이 됩니다.

dp[N] = dp[N-3] + dp[N-2] + dp[N-1] 입니다.

 

 

탑다운 방식으로 구현한 방식입니다.

get(int n) : n의 숫자를 1과 2, 3 으로 만들 수 있는 경우의 수를 반환한다.

 

n = 1을 만드는 경우는 1 -> 1가지

n = 2 를 만드는 경우는 1 + 1, 2  -> 2가지

n = 3 을 만드는 경우는 1 + 1 + 1, 1 + 2, 2 + 1, 3 -> 4가지입니다.

n = 0이거나 n < 0 이라면 더 이상 만들 수 없으므로 0 가지입니다.

 

위와 같은 기저사례를 만들고 재귀함수를 실행합니다.

 

코드

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());
    	
    	N = Integer.parseInt(st.nextToken());
    	
    	dp = new int[11];
    	
    	dp[1] = 1;
    	dp[2] = dp[1] + 1;
    	dp[3] = dp[1] + dp[2] + 1;
    	
    	for(int i=4;i<=10;i++) {
    		dp[i] = dp[i-1] + dp[i-2] + dp[i-3]; 
    	}
    	for(int t = 0; t<N;t++) {
    		st = new StringTokenizer(br.readLine());
        	System.out.println(dp[Integer.parseInt(st.nextToken())]);
    	}
    	
    }
    
    
}

 

package Main;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    public static int N, T, M; 
    public static int answer = 0;
    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[11];
		Arrays.fill(cache, -1);
		while(T-- > 0) {
			st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken());
			System.out.println(get(N));
		}
	}
    
    public static int get(int n) {
    	if(n < 0) return 0;
    	if(n == 0) return 0;
    	if(n == 1) return 1;
    	if(n == 2) return 2;
    	if(n == 3) return 4;
    	if(cache[n] != -1) return cache[n];
    	
    	int ret = 0;
    	ret += get(n - 1);
    	ret += get(n - 2);
    	ret += get(n - 3);
    	
    	return cache[n] = ret;
    }
    
}