[C++] BOJ 9095 / DP (1, 2, 3 더하기)

문제 분석

 

https://www.acmicpc.net/problem/9095

해당 문제도 DP로 해결해야 한다. DP의 경우에는 정말 어려운 문제가 아닌 이상, 문제 분석과 해결 방법은 생략하겠다.

 

코드

#include <iostream>
using namespace std;
int arr[12] = {0,1,2,4,0,0,0,0,0,0,0,0};

int main() {
    int t, n;
    cin >> t;
    while(t--) {
        cin >> n;
        if(n<=3) {
            cout << arr[n] << "\n";
            continue;
        }
        for(int i=4;i<=n;i++) {
            arr[i] = arr[i-1] + arr[i-2] + arr[i-3];
        }
        cout << arr[n] << "\n";
    }
}

 

점화식

arr[i] = arr[i-1] + arr[i-2] + arr[i-3]