BOJ-15990 1,2,3 더하기 5

필요한 지식

1. 동적계획법

접근

• n이 100,000 까지.

• 같은수를 두번 이상 연속해서 사용하면 안된다.

• 점화식

for (int k = 1; k <= 3; k++) {
			dp[i][k - 1] = (dp[i - k][0] + dp[i - k][1] + dp[i - k][2] - dp[i - k][k - 1]) % MOD;
		}

• dp[i][j] : i의 합이 j+1로 끝나는 경우의 수

• i가 1로 끝났을 경우 dp[i-1][1]과 dp[i-1][2]를 더한 값을 가진다.

• i가 2로 끝났을 경우 dp[i-1][0]과 dp[i-1][2]를 더한 값을 가진다.

• i가 3으로 끝났을 경우 dp[i-1][0]과 dp[i-1][1]를 더한 값을 가진다.

코드(C++)

#include <iostream>
#include <vector>
#include <algorithm>
#define MOD 1000000009
using namespace std;
typedef long long ll;
ll t, n;
ll dp[1000001][3];
int main() {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	dp[1][0] = dp[2][1] = dp[3][0] = dp[3][1] = dp[3][2] = 1;
	for (int i = 4; i <= 100000; i++) {
		for (int k = 1; k <= 3; k++) {
			dp[i][k - 1] = (dp[i - k][0] + dp[i - k][1] + dp[i - k][2] - dp[i - k][k - 1]) % MOD;
		}
	}
	cin >> t;
	while (t--) {
		cin >> n;
		ll sum = 0;
		for (int i = 0; i < 3; i++)
			sum += dp[n][i] % MOD;
		cout << sum % MOD << "\n";
	}
	return 0;
}