[DP #24] (BOJ 2225) 합분해

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

2225번: 합분해

문제

0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구하는 프로그램을 작성하시오.

덧셈의 순서가 바뀐 경우는 다른 경우로 센다(1+2와 2+1은 서로 다른 경우). 또한 한 개의 수를 여러 번 쓸 수도 있다.

입력

첫째 줄에 두 정수 N(1 ≤ N ≤ 200), K(1 ≤ K ≤ 200)가 주어진다.

출력

첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다.

 

---

접근법

기존 문제들과 비슷하게 풀 수 있다

이 문제는 수 N과 개수 K 두 개의 변수가 필요하므로 이차원 배열로 해결할 수 있다고 생각했다.

 

DP[K][N] = res

위 식을 K개의 수로 N을 만드는 경우의 수 res로 두고 풀자.

 

예를 들어 DP[1][3]은 무엇일까?

3 하나로 만들 수 밖에 없기 때문에 1이다.

 

다른 수들도 마찬가지로 한 개의 수로 만들 수 있는 경우의 수는 1이다.

따라서, 기본값을 다음과 같이 설정한다.

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

 

DP[2][3]는 무엇일까?

표로 표현하면 알아보기 훨씬 쉽다.

DP[2][3]은 1개로 만든 수를 모두 더한 것과 같다.

 

여기서 주의할 점은 0으로 만드는 경우도 포함시켜야한다.

따라서 DP[1][3] = 1 {3}에 0을 더한 {3, 0}을 포함해야한다.

 

이를 통해 점화식을 도출 가능하다.

 

코드

#include <iostream>

#define MAX 201

using namespace std;

int arr[MAX];
int dp[MAX][MAX];
int n, m;

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

int main() {
	
	cin >> n >> m;

	init();

	for (int i = 2; i <= m; i++) {
		for (int j = 0; j <= n; j++) {
			for (int k = 0; k <= j; k++) {
				dp[i][j] += (dp[i - 1][k]);
				dp[i][j] %= 1000000000;
			}
		}
	}

	cout << dp[m][n]%1000000000;
}