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

<정답>

import java.io.*;

class Main{
    public static void main(String args[]) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] dp = new int[11];
        StringBuilder sb = new StringBuilder();
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 4;

        for(int i=0; i<n; i++){
            int x = Integer.parseInt(br.readLine());
            for(int j=3; j<x+1; j++){
                if(dp[j]>0) continue;
                dp[j] = dp[j-3] + dp[j-2] + dp[j-1];
            }
            sb.append(dp[x]).append("\n");
        }

        System.out.print(sb);
    }
}

1. 테이블 정의
dp[i] = i를 1,2,3으로 나타내는 방법의 수

 

2. 점화식 찾기 : 앞 3개 더하기

[1] 1
[2] 2
[3] 4


[4] 7
1111
112
22
13

[5] 13
1+1+1+1+1 >1
1+1+1+2 > 4
1+1+3 > 3
1+2+2 > 3
2+3 > 2

[6] 24
1+1+1+1+1+1 >1
1+1+1+1+2 > 5
1+1+1+3 > 4
1+1+2+2 > 6
1+2+3 > 6
3+3 > 1
2+2+2 >1

[7] 44
1+1+1+1+1+1+1 >1
1+1+1+1+1+2 >6
1+1+1+1+3 >5
1+1+1+2+2 >10
1+1+2+3 >12
1+2+2+2 >4
1+3+3 >3
2+2+3 > 3

3.초깃값: 1,2,3

 

 

그래도 dp 문제 좀 풀다보니까 약간 감이 온다.

근데 vs code에서 돌리니까 Build fail 뜨는데 왜그러는거지?