[c++][BOJ][9095] 1, 2, 3 더하기

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

9095번: 1, 2, 3 더하기

특정 숫자를 1, 2, 3 으로 더해서 만드는 문제입니다.

 

이전 타일 문제랑 비슷하게 , n번째 수를 만드는 것은

 

n - 1 번째 수에 1을 더한 경우 ,

n - 2 번째 수에 2를 더한 경우, 

n - 3 번째 수에 3을 더한 경우 

 

3가지로 나눌 수 있습니다.

 

즉, n번째 수는 (n - 1) + (n - 2) + (n - 3) 가지 경우의 수가 나옵니다.

#include <iostream>
using namespace std;

int main(){
    int testcase;
    cin >> testcase;
    
    for(int i=0; i<testcase; i++){
        int n;
        cin >> n;
        
        int arr[20] = {0};
    
        arr[1] = 1;
        arr[2] = 2;
        arr[3] = 4;

        int index = 4;

        while(index <= n){
            arr[index] = arr[index-1] + arr[index-2] + arr[index-3];
            index++;
        }

        cout << arr[n] << '\n';
    }
}