백준 9095번 1,2,3 더하기

문제 링크 : www.acmicpc.net/problem/9095

9095번: 1, 2, 3 더하기

이 문제는 백준 11727번 2xn 타일링2와 유사하다.

결국 11727번과 동일하게 마지막을 1로 더하는 방법, 2로 더하는 방법, 3으로 더하는 방법을 고려하여 점화식을 세우면 된다.

다만 한 가지 주의해야할 점은, 1+1+2와 1+2+1, 2+1+1 모두 다른 계산식으로 인정한다는 점이다.

 

#include <iostream>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int n= 0 , temp = 0, arr[12];
    cin >> n;
    arr[0] = 0;
    arr[1] = 1;
    arr[2] = 2;
    arr[3] = 4;
    for(int i=4; i<=11; i++) arr[i] = arr[i-3]+arr[i-2]+arr[i-1];
    while(n--){
        cin >> temp;
        cout << arr[temp] << "\n";
    }
    return 0;
}