[BOJ 9095] 1, 2, 3 더하기

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

 

풀이 :

 

DP문제입니다.

1, 2, 3으로 새로운 방법을 만들 수 있는 경우는

i-1인 경우 : + '1'

i-2인 경우 : + '2'

i-3인 경우 : + '3'

이 세가지 경우 입니다.

따라서, cache[i] = cache[i-1]+cache[i-2]+cache[i-3]대로 쌓으면 됩니다.

 

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