[BOJ 15989] 1,2,3 더하기4

DP 문제 인 것을 인식하고 풀었는데도 많이 어려웠다.

 

해설을 위해서 아래 내용을 보자

 

우선 행의 경우 각 숫자의 순서를 나타내고 열의 경우 1,2,3 의 숫자가 마지막에 나올 때의 갯수를 표시한다.

 

아래 식은 갯수를 표시하지 않고 실제 식으로 표현을 하였다.

 

dp[1][1] - 1
dp[1][2] - 0
dp[1][3] - 0

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

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

dp[4][1] - (1 + 1 + 1) + 1
dp[4][2] - (1 + 1) + 2 , 2 + (2)
dp[4][3] - (1) + 3

dp[5][1] - (1 + 1 + 1 + 1) + 1
dp[5][2] - (1 + 1 + 1) + 2 , + (1 + 2) + 2  
dp[5][3] - (1 + 1) + 3 , (2) + 3

 

위 dp를 자세히 살펴보면 수식을 반복해서 앞의 배열으로 부터 가져와서 사용하는 것을 볼 수 있다.

 

즉, 점화식을 위 식을 기반으로 뽑아내면 아래와 같다.

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

아래는 전체 코드이다.

import java.util.*;

public class BOJ_15989 {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        int dp[][] = new int[10001][4];
        dp[1][1] = 1;
        dp[1][2] = 0;
        dp[1][3] = 0;
        dp[2][1] = 1;
        dp[2][2] = 1;
        dp[2][3] = 0;
        dp[3][1] = 1;
        dp[3][2] = 1;
        dp[3][3] = 1;
        for(int i = 4; i < 10001; 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 t = 0; t < T; t++){
            int n = sc.nextInt();
            System.out.println(dp[n][1] + dp[n][2] + dp[n][3] );
        }
    }
}

 

15989번: 1, 2, 3 더하기 4