1. 발상
간단한 dp를 이용해 문제를 해결했다.
i의 합 -> (i-1)의 합 + (i-2) 의 합 + (i-3) 의 합
base case -> (dp[1] = 1, dp[2] =2, dp[3] = 4) 로 설정한다.
2. 소스코드
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int dp[12] = {0, };
int main(){
cin.tie(NULL); ios::sync_with_stdio(false);
int T;
cin >> T;
dp[1] = 1;
dp[2] = 2;
dp[3] = 4;
for(int i=4; i<12; i++){
dp[i] = dp[i-1] + dp[i-2] + dp[i-3];
}
for(int i=0; i<T; i++){
int N;
cin >> N;
cout << dp[N] << "\n";
}
}
dp 부분만 따로 보면 다음과 같다.
dp[1], dp[2], dp[3]의 base case 설정
-> for문으로 dp값 계산 후 배열에 채워넣기
dp[1] = 1;
dp[2] = 2;
dp[3] = 4;
for(int i=4; i<12; i++){
dp[i] = dp[i-1] + dp[i-2] + dp[i-3];
}