BOJ [2225] 합분해

https://www.acmicpc.net/problem/2225

1. 분류

다이나믹 프로그래밍

2. 풀이

규칙만 찾으면 금방 풀리는 문제이다.

나는 이런 류의 문제에서 규칙성이 있겠다 판단되면 엑셀을 켜고 하나하나 대입하여 확인한다.

대부분의 경우에 규칙이 적용되면 금방 구할 수 있기 때문이다.

N, K에 숫자를 0, 0부터 대입하여 몇 개 구하면 바로 알 수 있다.

3. 소스코드

#include <cstdio>
typedef long long ll;
ll d[201][201];
ll mod = 1000000000LL;

int main()
{
	int n, k;
	scanf("%d %d", &n, &k);

	for (int i = 1; i <= k; i++)
		d[i][0] = 1LL;

	for (int i = 1; i <= n; i++)
	{
		d[1][i] = i;
		d[2][i] = (i + 1LL);
	}

	for (int i = 1; i <= n; i++)
	{
		for (int j = 3; j <= k; j++)
			d[j][i] = (d[j - 1][i] % mod + d[j][i - 1] % mod) % mod;
	}

	printf("%lld\n", d[k][n]);

	return 0;
}