[BOJ/C++]2225(합분해)

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

비슷한 문제: (2579)계단 오르기
Link: https://www.acmicpc.net/problem/2579

• 문제를 잘 봐야한다. 필자의 경우 문제를 잘못 이해하여(0이 왜 필요하지..? 라는 이상한 발상 등) 시간이 오래 걸렸기에 혹여 이 글을 읽는 분들은 문제를 잘못 읽는 실수를 범하지 않기를 바랍니다.

1. 경우의 수 구하기 -> 아마도 DP가 아닐까라는 생각(성급한 일반화지만 보통 경우의 수를 구할 때 DP를 많이 사용한 것 같음)
2. 덧셈의 순서가 바뀐 경우는 다른 경우로 센다
   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;
}