- 백준 9095 : 1, 2, 3 더하기
- DP
- https://www.acmicpc.net/problem/9095
- 1로 만들기 와 유사했던 문제 (그래도 삽질 오래함)
f(n) = f(n-1) + f(n-2) + f(n-3)
을 사용하면 금방 풀 수 있다.
#include <iostream>
using namespace std;
int cache[11];
void dp(){
cache[1] = 1; // 1
cache[2] = 2; // 1+1, 2
cache[3] = 4; // 1+1+1, 1+2, 2+1, 3
for(int i=4; i<=11; i++){
cache[i] = cache[i-1] + cache[i-2] + cache[i-3];
}
}
int main(void){
int t, n;
cin >> t;
dp();
for(int i=0; i<t; i++){
cin >> n;
cout << cache[n] << endl;
}
return 0;
}