Link: https://www.acmicpc.net/problem/2225
비슷한 문제: (2579)계단 오르기
Link: https://www.acmicpc.net/problem/2579
- 경우의 수 구하기 -> 아마도 DP가 아닐까라는 생각(성급한 일반화지만 보통 경우의 수를 구할 때 DP를 많이 사용한 것 같음)
- 덧셈의 순서가 바뀐 경우는 다른 경우로 센다
2-1. 처음에는 n!/(r!k!j!)과 같은(명칭을 까먹었다..) 방식으로 풀어야되나 고민하였음
2-2. 허나 구현이 과하게 다이나믹해질 것으로 생각되고, 문제가 그런 걸 바라지도 않을 것이라 생각함
2-3. 비슷하다 해야할지 마침 계단 오르기(2579) 문제가 생각났고, 2차원 DP배열 생성 및 점화식을 세워 문제를 풀어나감
점화식은 다음과 같이 만들었고, 해당 점화식을 기반으로 2중 for문을 돌려 정답을 얻었다.
DP[i][j] = DP[i - 1][j] + DP[i][j - 1]
#include<iostream>
#include<cmath>
using namespace std;
#define MAX 201
int dp[MAX][MAX]; //row: n, col: k
int n, k;
void input() {
cin >> n >> k;
}
void solution() {
input();
int maxVal = max(n, k);
for (int i = 1; i <= maxVal; ++i) {
dp[1][i] = i;
dp[i][1] = 1;
}
for (int i = 2; i <= maxVal; ++i) {
for (int j = 2; j <= maxVal; ++j) {
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
dp[i][j] %= 1'000'000'000;
}
}
cout << dp[n][k];
}
int main() {
cin.tie(0), cout.tie(0), ios_base::sync_with_stdio(0);
solution();
return 0;
}