백준 15988 c++

DP 푸는법 1. 패턴 찾아보기

#include <iostream>
#include <vector>
#define MOD 1000000009

using namespace std;

void make_DP(vector<long long>& DP) {
	int i, j;

	DP[0] = 1;
	DP[1] = 1;
	DP[2] = 2;
	for (i = 3; i < DP.size(); i++) {
		DP[i] = (DP[i - 3] + DP[i - 2] + DP[i - 1]) % MOD;
	}

	return;
}

int find_answer(int n, vector<long long> &DP) {
	int answer = 0;
	int i, j;
	
	answer = DP[n];

	return answer;
}

int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int T, i, n;
	vector<long long> DP(1000001, 0);

	make_DP(DP);

	cin >> T;
	for (i = 0; i < T; i++) {
		cin >> n;
		cout << find_answer(n, DP) << "\n";
	}

	return 0;
}