9095

풀이코드

#include <iostream>
using namespace std;

// 9095

int main(){
	int N[100], T, maxN = -1;
    int n[11];
	
	n[1] = 1;
    n[2] = 2;
	n[3] = 4;

	cin >> T;
	cin.ignore();
		
	for(int i = 0; i < T; i++){
		cin >> N[i];
		if(maxN < N[i]) maxN = N[i];
	}

    for (int i = 4; i <= maxN; i++) {
        n[i] = n[i - 1] + n[i - 2] + n[i - 3];
    }

	for(int i = 0; i < T; i++){
		cout << n[ N[i] ] << endl;
	}
}

 

해설

 

처음 점화식을 찾는 과정만 착실히 밟으면 구현 자체는 어렵지 않았다.

$$a_n = a_{n-1} + a_{n-2} + a_{n-3}$$

테스트 케이스 중 가장 큰 N 값을 찾아서, 전체 범위인 11까지 구하는 것이 아니라, N 까지만 점화식을 풀어나가는 것이 더 빠른 구현의 핵심이었다.