[백준 9095] 1,2,3 더하기 -JAVA //le_effort

전형적인 DP문제이다

 

일단 점화식은

dp [i] = dp[i-1]+dp[i-2]+dp[i-3] 인데 이걸 어떻게 도출하는지에 대해서 설명하겠다

 

모든 수를 1 , 2, 3 을 이용해서 만들어야 한다.

dp[i] 는 i번째 수를 만들 수 있는 개수로 하겠다

 

dp [1] = 1                          총 1개

dp[2] = 1+1 / 2                  총 2개

dp[3] = 1+1+1 , 1+2, 2+1, 3  총 4개

 

이제 dp[4]이상을 구해보자

dp[4]는 위 문제에도 나와있다.

(1+1+1+1)  (1+2+1) (2+1+1)  (3+1) (1+1+2) (2+2)  (1+3)

 

자 이제 규칙을 찾기 위해 색을 칠하겠다.

(1+1+1+1)  (1+2+1) (2+1+1)  (3+1) (1+1+2) (2+2)  (1+3)

 

색칠된 부분을 보자.  

초록색으로 색칠된 것들은 dp[3]을 만드는것에 1을 더해준 것이고

파란색으로 색칠된 것들은 dp[2]을 만드는 것에 2를 더해준 것

빨간색으로 색칠된 것들은 dp[1]을 만드는 것에 3을 더해준 것이다.

 

n이 4일 경우

dp[3]을 만드는 경우의 수에 1을 더해주는것,  dp[2]을 만드는 경우의수에 2를 추가하는것 dp[1]을 만드는 경우의수에 3을 더해주는 것이다.

 

즉 dp[n] = dp[n-1]+dp[n-2]+dp[n-3]이다.

 

import java.io.*;
import java.util.*;
public class Main {
    static int n;
    static int t;
    static int dp[];
    static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        t = Integer.parseInt(br.readLine());
        dp = new int[12];
    
        
        dp[1]=1;    // 1+1
        dp[2]=2;    //1+1  2
        dp[3]=4;    // 1+1+1 2+1 1+2 3
        
        for(int i=4; i<=11; i++) {
            dp[i] = dp[i-1]+dp[i-2]+dp[i-3];
        }
        
        while(t-->0) {
            n = Integer.parseInt(br.readLine());
            sb.append(dp[n]+"\n");
        }
        System.out.println(sb);
    }
}