문제
https://www.acmicpc.net/problem/2225
풀이
중복조합으로 풀려다가 오버플로우 나고 머리털 다 빠질뻔 ;
✨ N과 (N-1)이 특정 관계를 갖고 있으면 DP 이용했을 때 가장 효율적이라는 것 잊지 말기 !!
=> n과 k는 (n-1, k)일 때의 방법과 (n, k-1)일 때의 방법의 합
코드
#include <iostream>
using namespace std;
int dp[201][201];
int main() {
int n, k;
cin >> n >> k;
for (int i = 0; i <= k; i++)
dp[1][i] = i;
for (int i = 2; i <= n; i++) {
for (int j = 1; j <= k; j++) {
dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]) % 1000000000;
}
}
cout << dp[n][k];
return 0;
}
👩🏻💻