BOJ-15993 1,2,3 더하기 8

필요한 지식

1. 동적계획법

접근

• n이 100,000 까지

• n을 1,2,3의 합으로 나타냈을 때 사용한 숫자가 홀수개, 짝수개 인 경우의 수를 구분하여 출력해야한다.

• 점화식

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

• dp[i][0] : i의 합을 1,2,3을 이용하여 홀수개로 나타낸 경우의 수

• dp[i][1] : i의 합을 1,2,3을 이용하여 짝수개로 나타낸 경우의 수

• i가 1로 끝났을 경우 dp[i][0]에 dp[i-1][1]을 dp[i][1]에 dp[i-1][0]을 더한다.

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

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

코드(C++)

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

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