BOJ-15988-1,2,3 더하기 3

필요한 지식

1. 동적계획법

접근

• n이 1,000,000 까지 커졌다.

• 점화식

dp[i] = dp[i-1]+dp[i-2]+dp[i-3]
dp[i] : i를 1,2,3 의 합으로 나태내는 방법의 수

• i가 1,2,3 일경우 각각 1,2,4로 초기화 시켜준다.

코드(C++)

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