백준2225 - 합분해

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

2225번: 합분해

2차원 배열을 사용한 DP를 구현한 문제다. 점화식을 잘 도출하면 금방 해결할 수 있는 문제다. 10억으로 나누는 나머지를 저장한다는 것을 잊지 말아야 한다.

 

#include <iostream>
using namespace std;
int main() {
	long long int mat[201][201]; //DP의 결과
	int N, K; //N을 만들기 위해 K개의 수를 사용한다.
	int ans_x = 1, ans_y = 1; //답으로 출력해야 하는 점화식 결과의 순서를 결정

	cin >> N >> K;

	//숫자 한 개로 덧셈을 구현하는 경우의 수는 모두 1이다.
	for (int i = 0; i <= N; i++) {
		mat[1][i] = 1;
	}

	//숫자 두 개 이상으로 구현하는 경우는 m[x][i] = m[x][i-1] + m[x-1][i]이다
	for (int i = 2; i <= K; i++) {
		mat[i][0] = 1;
		for (int j = 1; j <= N; j++) {
			mat[i][j] = (mat[i][j - 1] + mat[i - 1][j]) % 1000000000;
			ans_x = i;
			ans_y = j;
		}
	}

	cout << mat[ans_x][ans_y];
}