[C++] 백준 15988번 1, 2, 3 더하기 3

다이나믹 프로그래밍 문제입니다.

BOTTOM-UP방식으로 1부터 찾는 수까지 차례대로 만들어가면 됩니다.

1, 2, 3으로 더하므로 N은 다음으로 만들 수 있습니다.
N - 1 (1로 더한 경우) 
N - 2 (2로 더한 경우)
N - 3 (3로 더한 경우)

이를 점화식으로 표현하면 다음과 같습니다.

DP[i] = DP[i - 1] + DP[i - 2] + DP[i - 3]

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

typedef long long ll;
int DP[1000001];

int main(int argc, char* argv[])
{
	int ts;
	ll num;
	ll maxNum = 0;
	vector<ll> v;

	memset(DP, 0, sizeof(DP));

	cin >> ts;

	while (ts--) {
		cin >> num;
		v.push_back(num);

		maxNum = max(maxNum, num);
	}

	DP[1] = 1;
	DP[2] = 2;
	DP[3] = 4;

	for (int i = 4; i <= maxNum; ++i) {
		DP[i] = (((DP[i - 1] + DP[i - 2]) % 1000000009) + DP [i - 3]) % 1000000009;
	}

	for (int i = 0; i < v.size(); ++i) {
		cout << DP[v[i]] << endl;
	}

	return 0;
}