2225(dp)

첫인상

수학 문제가 아닐까 생각했었다 하지만 출력이 1000000000으로 나눈 값이라서 시간 초과가 나지 않을까 추측해서 다른 풀이를 생각했다

문제상황

dp로 푸는 문제라는 것은 인지했고 n , k를 변수로 두는 2차원 dp 라는 것도 인지했지만 점화식이 도저히 만들어지지 않아서 엄청나게 고생했다

풀이

dp[n][k] 가 의미하는 것이 k개를 더해서 n이 되는 경우의 수이다
k-1개를 더해서 n이 되는 경우의 마지막에 + 0을 하는 경우의 수 dp[n][k-1]
k개를 더해서 n-1이 되는 경우의 마지막 수에 + 1을 하는 경우의 수 dp[n-1][k]
두개를 더한 것이 dp[n][k]가 된다
그러므로 dp[n][k] = dp[n-1][k] + dp[n][k-1]이 점화식이다

코드

#include<iostream>
using namespace std;

long dp[205][205];

long solve(int n, int k) {
	if (k == 1) {
		return 1;
	}
	else if (n == 1) {
		return k;
	}

	if (dp[n][k] != 0) {
		return dp[n][k];
	}
	else {
		dp[n][k] = (solve(n - 1, k) + solve(n, k - 1)) % 1000000000;
		return dp[n][k];
	}
}

int main() {
	int n, k;

	cin >> n >> k;

	for (int i = 1; i <= n; i++) {
		dp[i][1] = 1;
	}

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

	cout << solve(n, k);
}