BOJ-15991 1,2,3 더하기 6

필요한 지식

1. 동적계획법

접근

• n이 100,000 까지.

• 합이 대칭을 이루어야한다.

• 점화식

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

• dp[i] : i의 합을 1,2,3을 이용하여 대칭을 이루게 한 경우의 수

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

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

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

• i-2*k의 값이 i와 같다면 k+k형태가 존재하는 것이므로 1을 더해준다.

코드(C++)

#include <iostream>
#include <vector>
#include <algorithm>
#define MOD 1000000009
using namespace std;
typedef long long ll;
ll t, n;
ll dp[1000001];
int main() {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	dp[1] = 1;
	dp[2] = dp[3] = 2;

	for (int i = 4; i <= 100000; i++) {
		for (int k = 1; k <= 3; k++) {
			if (i - k * 2 > 0)dp[i] += dp[i - k * 2];
			if (i - k * 2 == 0) dp[i] += 1;
		}
		dp[i] %= MOD;
	}
	cin >> t;
	while (t--) {
		cin >> n;
		cout << dp[n] % MOD << "\n";
	}
	return 0;
}