BOJ-16195 1,2,3 더하기 9

필요한 지식

1. 동적계획법

접근

• n이 1,000 까지, m도 1,000까지

• n을 1,2,3의 합으로 나타냈을 때 사용한 수의 개수가 m개 이하인 경우의 수를 구해야한다.

• 점화식

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

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

• i가 j개의 숫자로 나타낸 경우(dp[i][j])는

• i가 1로 끝났을 경우 dp[i-1][j-1]값에

• i가 2로 끝났을 경우 dp[i-2][j-1]을 더하고

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

코드(C++)

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

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