[백준][9095번][DP] 1,2,3 더하기

1,2,3 더하기

https://www.acmicpc.net/problem/9095

<코드>

#include <stdio.h>
 
int main(void){
    int testcase;
    scanf("%d", &testcase);
    while (testcase--){
        int Dp[15] = {};
        Dp[0] = 1;
        int K;
        scanf("%d", &K);
 
        for (int i = 1; i <= K; i++){
                
            if (i-1>=0)
                Dp[i] += Dp[i - 1];
            if (i - 2 >= 0)
                Dp[i] += Dp[i - 2];
            if (i - 3 >= 0)
                Dp[i] += Dp[i - 3];
        }
 
        printf("%d\n", Dp[K]);
 
    }
    return 0;
}

<문제 푼 요령>

 1. 이 문제 같은경우는 1,2,3 만 고려해줘야하기 때문에 푸는 방법이 어렵지 않다.

 2. 각 숫자에 대해서 어떤 경우의 수가 있을지만 생각하면 된다. 

 3. 간단하게 앞자리 수에 1, 2, 3 이 나올 경우를 생각해 보면 된다. 즉 예를 들면 숫자 4 같은경우는 앞에 1이 추가됬을때 1  -> 4-1 인 3을 만드는 모든 경우의  수가 되고 2가 추가된다면 -> 4-2 인 2를 만드는 모든 경우의 수를 추가하고 3을 앞에 추가하면 3-1인 1을 만드는 모든 경우의 수를 추가하면 된다.

 4. 즉 Dp[i] += Dp[i-1]  , Dp[i] += Dp[i-2] , Dp[i] += Dp[i-3] 의 값을 꾸준히 더해주면서 구하면되는데 계산을 쉽게 하기위해 Dp[0]의 경우를 1로 채워 넣는다.