[baekjoon 2225] 합분해- DP(동적 프로그래밍) (C++)

www.acmicpc.net/problem/2225

2225번: 합분해

문제의 조건은 N, K가 주어졌을 때 N을 K개의 숫자로 구성하는 경우의 수를 구하는 것이다.

 

예시로 N이 2이고 K 또한 2이면 경우의 수는 3개로 (0,2), (1,1), (2,0)이다. (0을 포함하고, 1-2, 2-1은 각각 카운트된다.)

 

DP 배열은 2차원 배열로 구성되며, DP[N][K]로 N을 K개로 구성하는 경우의 수를 저장해주었다.

 

또한 순서가 있는 경우의 수이므로 순열의 경우로 생각해야 하며, 세 자릿수의 순열은 3!이다. 네 자릿수는 4!

 

DP[0][2] ~ DP[N][2]배열엔 각각 2개로 0부터 N까지 구하는 경우의 수가 저장되어있고, 

그렇다면 DP[3][3]은 어떻게 구할까?

 

DP[0][2]엔 0,0

DP[1][2]엔 0,1 1,0

DP[2][2]엔 0,2 1,1 2,0

DP[3][2]엔 0,3 1,2 2,1 3,0이 있다. 즉 앞이 정해져 있고 뒤에 한 자리를 붙이기만 하면 세 자리로 3을 만드는 경우의 수가 만들어진다.

 

0,0 + 3 / 0,1 + 2 / 0,2 + 1 / 0,3 + 0 (첫 번째 수가 0인 경우)

1,0 + 2 / 1,1 + 1 / 1,2 + 0(첫 번째 수가 1인 경우)

2,0 + 1 / 2,1 + 0 (2인 경우)

3,0 + 0 (3인 경우)

으로 DP[3][3]은 DP[0][2] + DP[1][2] + DP[2][2] + DP[3][2]로 구성된다.

 

즉 DP[N][K] = DP[0][K-1] + ~  +DP[N][K-1]이다.

 

그런데 배열을 잘 살펴보면, DP[N-1][K](구하려는 N의 전 단계)까지는 DP[0][K-1] ~ + DP[N-2][K-1]의 합이 저장되어 있다.

따라서, 일일이 다 더해주기보다는 DP[N][K] = DP[N-1][K] + DP[N][K-1]으로 구하는 것이 더 빠를 것이다.

 

#include <iostream>
using namespace std;

#define mx  1000000000

long long dp[201][201], n, k;

int main() {
	cin >> n >> k; // k개 더해서 n을 완성
	
	for (int i = 0; i <= n; i++) {
		dp[i][1]= 1; // 어떤 수를 1개로 완성 = 자기 자신
	}
	for (int i = 1; i <= k; i++) {
		dp[0][i] = 1; // 0을 i개로 완성 = 0으로만 이루어진 1가지
	}

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= k; j++) {
			dp[i][j] = (dp[i - 1][j] + dp[i][j - 1])%mx;
		}
	}
	
	cout << dp[n][k];
}

숫자가 매우 커지므로 MOD연산을 통해 10억으로 나눠주어야 한다. 

또한 초기화는 DP[I][1]은 i를 1개로 구성하는 경우는 i 자기 자신밖에 없으므로 1로 초기화

DP[0][i]는 0을 i개로 구성하는 경우는 0, 00, 000, 0000 등 0으로 이루어진 1개밖에 없으므로 역시 1로 초기화해준다.