BOJ : 9095 1,2,3 더하기

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

출처

ACM-ICPC > Regionals > Asia > Korea > Asia Regional - Taejon 2001 PC번

DP로 해결할 수 있는 문제입니다.

1부터 4까지만 보면

dp[1] = 1

dp[2] = 1+1, 2

dp[3] = 1+2, 1+1+1, 2+1, 3

dp[4] = 1+3, 1+1+2, 2+2, 1+1+1+1, 1+2+1, 2+1+1, 3+1 

이렇게 된다. 

자세히보면 i번째 값은 i-1, i-2, i-3번째를 합한 값과 같다.

#include <stdio.h>
int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        int N, n[12];
        n[0]=0, n[1]=1, n[2]=2, n[3]=4;
        for(int i=4;i<=11;i++)
            n[i] = n[i-1]+n[i-2]+n[i-3];
        scanf("%d",&N);
        printf("%d\n",n[N]);
    }
}