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

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

dp[k]: k를 1,2,3의 합으로 나타낼 수 있는 경우의 수

dp[k] = dp[k - 1] + dp[k - 2] + dp[k - 3]

k - 1에서 +1을 해서 k를 만들 수 있고 나머지 k-2,k-3도 같은 방식으로 만들 수 있다.

#include <stdio.h>

int memo[11];

int f(int k)
{
    if (memo[k])
        return memo[k];
    return memo[k] = f(k - 1) + f(k - 2) + f(k - 3);
}
int main()
{
    int n;
    scanf("%d", &n);
    memo[1] = 1;
    memo[2] = 2;
    memo[3] = 4;
    while (n--)
    {
        int input;
        scanf("%d", &input);
        printf("%d\n", f(input));
    }
    return 0;
}