9095) 1,2,3 더하기

문제

입력으로 n의 테스트 케이스와 n개의 입력들(<12)이 주어진다.
이 입력값을 합으로 갖는 1, 2, 3의 덧셈 식의 갯수를 구해야 한다.

풀이

한참을 고민했는데, 아주 쉬운 문제였다.
예를 들어 4를 보자. 4= 1+3 즉, 1로 시작하는 식들이 있을 때의 경우의 수는 3을 구성하는 경우의 수와 같다.
또 4= 2+2 이므로 2로 시작하는 식들은 2를 구성하는 경우의 수와 같으며
마지막으로, 4 = 3+1 이므로, 3으로 시작하는 식들은 1을 구성하는 경우의 수와 같다.
즉, P(4) = P(3)+P(2)+P(1)

일반식

P(n) = P(n-1)+P(n-2)+P(n-3)

코드

#include <iostream>
#include <algorithm>
using namespace std;

int main(){
    int num,largest=-1;

    cin>>num;
    int *arr = new int[num];
    for(int i=0;i<num;i++){
        cin>>arr[i];
        largest = max(largest, arr[i]);
    }
    int *arr2 = new int[largest];
    arr2[0] = 1;
    arr2[1] = 2;
    arr2[2] = 4;
    for(int i=3;i<largest;i++){
        arr2[i] = arr2[i-1]+arr2[i-2]+arr2[i-3]; 
    }

    for(int i=0;i<num;i++){
        cout<<arr2[arr[i]-1]<<endl;
    }
    
       

}