[백준] 15989번 1, 2, 3 더하기 4 java

문제 풀이 과정

dp[i][1] = 합이 i일 때 끝이 1로 끝나는 경우의 수
dp[i][2] = 합이 i일 때 끝이 2로 끝나는 경우의 수
dp[i][3] = 합이 i일 때 끝이 3으로 끝나는 경우의 수

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

예를 들어 4일 경우

1. 1 + 1 + 1 + 1
   합이 3일 때 1로 끝나는 경우에 1만 더해준 것과 같다

즉 dp[4-1][1] = dp[1][1] 는 1+1+1였으므로 여기에 1을 더해주면 4가 된다.

2. 1 + 1 + 2, 2 + 2

합이 2일 때 1로 끝나는 경우, 2로 끝나는 경우 + 2

dp[4-2][1] + dp[4-2][2]

3. 1 + 3
   합이 1일 때 1로 끝나는 경우, 2로 끝나는 경우, 3으로 끝나는 경우 + 3

dp[4-3][1]+dp[4-3][2]+dp[4-3][3]

즉 3만큼 빼면 i-3 끝에 3을 추가로 더할 수 있어서
dp[i-3][1]+dp[i-3][2]+dp[i-3][3] = dp[i][3]을 만들 수 있다.
dp[i][2] = dp[i-2][1] + dp[i-2][2]
dp[i][3] = dp[i-3][1]

잠깐 헷갈렸던게 왜 dp[i-2][1] + dp[i-2][2] + dp[i-2][3] 이 dp[i][2]가 될 수 없나 고민했다. i-2의 합이 3으로 끝나는 경우도 있을 수 있지 않나 싶었다.

다시 생각해보니 dp[i][2]는 무조건 끝이 2로 끝나야하므로 dp[i-2][3]은 올 수 없다. dp[i-2][3]은 끝이 3으로 끝나는 경우이기 때문이다. dp[i][n]의 정의를 계속 생각해야되는 것이 중요하다는걸 깨달았다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

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

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

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