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

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

기본숫자는 1,2,3

n번째 숫자는 n-3번째 결과에 3을 더하고 n-2번재 결과에 2를 더하고 n-1번째 결과에 1을 더한것의 합계로 표현가능하다.

점화식

arr[0] = 1

arr[1] = 2

arr[2] = 4

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

C++ code

#include <iostream>
using namespace std;
int main(){
    int t;
    cin >> t;
    for(int tc = 0; tc < t; tc++){
        int n;
        cin >> n;
        int* arr = new int[n];
        arr[0] = 1;
        arr[1] = 2;
        arr[2] = 4;
        for(int i = 3; i < n; i++){
            arr[i] = arr[i-1] + arr[i-2] + arr[i-3];
        }
        cout << arr[n-1] << endl;
        delete[] arr;
    }
    return 0;
}