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

dp 문제다

테이블을 잡을 때 d[n][k]로 잡았다

숫자 n을 만들 때 마지막 수가 k인 경우의 수다

 

그럼 이 테이블을 사용해서 계속 채워나갈 수 있다

중복이 없다고했으니 우리는 정렬했다고 가정하고 마지막수가 가장 큰 수라고 생각하자

그럼 마지막 수가 1,2,3 오는 경우를 생각하면

d[n][2] = d[n-2][1~2]가 된다

왜냐면 마지막에 오는 가장 큰 수는 2이므로 1부터 2까지 보는것이다

아래부터 축적해나가면 된다

 

소스코드

#include <iostream>
using namespace std;
int n;
int d[10010][4];
 
int main() {
    scanf(" %d", &n);
 
    d[1][1] = d[2][1] = d[2][2] = d[3][1] = d[3][2] = d[3][3] = d[4][1] = d[4][3] = 1;
    d[4][2] = 2;
 
    for (int i = 5; i <= 10000; i++) {
        for (int j = 1; j <= 3; j++) {
            for (int k = 1; k <= j; k++) {
                d[i][j] += d[i - j][k];
            }
        }
    }
 
    for (int i = 0; i < n; i++) {
        int k; scanf(" %d", &k);
        printf("%d\n", d[k][1] + d[k][2] + d[k][3]);
    }
}