[백준 9059] 1, 2, 3 더하기

1. 점화식

 

1, 2, 3으로 시작 가능하므로 3가지 case가 있으며

1로 시작하는 경우는 dp[i-1]

2로 시작하는 경우는 dp[i-2]

3으로 시작하는 경우는 dp[i-3]

따라서, dp[i] = dp[i-3] + dp[i-2] + dp[i-1] 이 됨

 

2. 코드

#include <stdio.h>

int main()
{
    int t;
    scanf("%d", &t);

    for (int i = 0; i < t; i++) 
    {
        int n;
        scanf("%d", &n);
        int dp[11] = { 0,1,2,4 };
        for (int i = 4; i <= n; i++)
            dp[i] = dp[i - 3] + dp[i - 2] + dp[i - 1];
        printf("%d\n", dp[n]);
    }
    return 0;
}