dp[i] = dp[i-1]+dp[i-2]+dp[i-3]
dp[i] : i를 1,2,3 의 합으로 나태내는 방법의 수
#include <stdio.h>
#include <algorithm>
#include <string.h>
using namespace std;
int dp[15];
int go(int i) {
if (i == 1) return 1;
if (i == 2) return 2;
if (i == 3) return 4;
int& ret = dp[i];
if (ret != -1) return ret;
ret = 0;
return ret = go(i - 1) + go(i - 2) + go(i - 3);
}
int main() {
int n, x;
scanf("%d", &n);
memset(dp, -1, sizeof(dp));
for (int i = 0; i < n; i++) {
scanf("%d", &x);
printf("%d\n", go(x));
}
return 0;
}