9507번: Generations of Tribbles

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


$O(n)$

문제에 주어진 점화식을 구현한다.

#include<cstdio>
int t, n;
long long dp[68] = { 1,1,2,4 };
int main() {
    for (int i = 4; i < 68; i++) dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3] + dp[i - 4];
    scanf("%d", &t);
    while (t--) scanf("%d", &n), printf("%lld\n", dp[n]);;
    return 0;
}