[백준 9095] 1, 2, 3 더하기 (DP)

 

 

 

 

DP 연습중 ... 접근을 거의 다 했는데 뒷심 부족인가... ㅠ 다해놓고 구현 못함

 

1을 만드는 경우 dp[1] = (1) -> 1개

2를 만드는 경우 dp[2] = (2), (1, 1) -> 2개

3을 만드는 경우 dp[3] = (3), (1, 1, 1), (1, 2), (2, 1) -> 4개

 

4를 만드는 경우

dp[4]

1, 1, 1, 1

1, 1, 2

1, 2, 1

1, 3

2, 1, 1

2, 2

3, 1

 

1 + 3 ( 앞이 1일 때, 3을 만드는 경우의 수 ) -> 4개

2 + 2 ( 앞이 2일 때, 2를 만드는 경우의 수 ) -> 2개

3 + 1 ( 앞이 3일 때, 1을 만드는 경우의 수 ) -> 1개

 

dp[n] = dp[n - 1] + dp[n - 2] + dp[n - 3]

 

import java.util.*;

public class Main {
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in); 
        int t = sc.nextInt();
        
        int[] dp = new int[11];
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 4;
        
        for(int i = 4; i <= 10; i++) {
            dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
        }
        
        for(int i = 0; i < t; i++) {
            int n = sc.nextInt();
            System.out.println(dp[n]);
        }
    }
}