백준 9095 1, 2, 3 더하기 c++

 

 

 

작성한 코드는 다음과 같다.

이렇게 점화식을 찾아 다이나믹 프로그래밍으로 구현하는 문제는,

처음 dp[1], dp[2], dp[3] ... 정도를 직접 계산하며 앞뒤와의 관계를 직접 찾아내 점화식을 구하는 것이 중요했다.

#include <iostream>
using namespace std;

int main(){
    int t;
    cin >> t;
    
    int dp[1001];
    dp[1] = 1; dp[2] = 2; dp[3] = 4;
    for(int i=4; i<=10; i++)
        dp[i] = dp[i-1] + dp[i-2] + dp[i-3];
    
    int n;
    for(int i=0; i<t; i++) {
        cin >> n;
        cout << dp[n] << "\n";
    }
    
    return 0;
}