[백준] 9095번 1,2,3 더하기

문제 링크: https://www.acmicpc.net/problem/9095

문제 및 입출력

문제 접근

보자마자 dp문제 인 것을 인식했다. 하지만, 점화식을 찾아내는 데 어려움을 겪었다. 점화식을 찾아낼 때는 규칙을 알 때까지, 작은 수 부터 계속 구해보는 것이 매우 중요한 것 같다.
점화식 : f(n) = f(n-3) + f(n-2) + f(n-1)

코드 구현(c++)

#include <iostream>

using namespace std;

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int testcase;
    cin >> testcase;
    int dp[12];
    dp[1] = 1;
    dp[2] = 2;
    dp[3] = 4;
    //점화식 : f(n) = f(n-3) + f(n-2) + f(n-1)
    for(int i = 4 ; i < 11 ; i++){
        dp[i] = dp[i-3] + dp[i-2] + dp[i-1];
    }
    while(testcase--){
        int num;
        cin >> num;
        cout << dp[num] << "\n";
    }
    
}