[백준 JAVA] 9095번 풀이 - 1, 2, 3 더하기 (DP)

 

생각의 방향 

11 미만의 자연수를 1,2,3의 조합을 더해서 만들 수 있는 경우의 수를 구해야한다. 

점화식을 찾는게 참 어려웠다... DP 문제를 여러개 풀면 익숙해질까!

 

문제를 더 작은 문제로 쪼개기

 

주어진 문제를 더 작은 문제로 쪼개는 것이 DP 문제를 푸는 시작이다.

해당 문제에 먼저 주어진 1, 2, 3 의 경우의 수를 찾는다. 

 

dp[0] = 0 

dp[1] = (1)

dp[2] = (1+1) , (2)

dp[3] = (1+1+1) , (1+2) , (2+1) , (3)

 

위에 알고 있는 0,1,2,3의 경우의 수를 가지고 dp 문제를 풀어야한다. 

dp[4] 의 경우의 수를 가져와서 살펴보면, 

1 + 1 + 1 +1

2 + 1 + 1

1 + 2 + 1

3 + 1

1 + 1 + 2

2 + 2

1 + 3

 

오렌지색 부분은 dp[3] 의 경우의 수들과 동일한 것이 보인다. 

1 + 1 + 2 에서 1 + 1 부분과 2 + 2 에서 2 는 dp[2] 의 경우의 수와 동일하다.

1 + 3 에서 1 은 dp[1] 의 경우의 수와 동일하다.

🔥 그럼 점화식은 dp[i] = dp[i-1] + dp[i-2] + dp[i-3] ; 이 된다. (i-3 까지의 경우의 수를 다 더한다.)

 

코드

package quiz;

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

public class _9095 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());
        int [] dp = new int[11];

        dp[3] = 4;
        dp[2] = 2;
        dp[1] = 1;
        for(int j=4; j<=10; j++){
            dp[j] = dp[j-1] + dp[j-2] + dp[j-3];
        }

        for(int i=0; i<t; i++){
            int n = Integer.parseInt(br.readLine());
            System.out.println(dp[n]);
        }
    }
}