백준 2225 : 합분해

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

2225번: 합분해

 

DP로 풀 수 있는 문제다.

 

DP[N][K]라고 할 때,

 

1. 1 ~ K개의 수로 0을 만드는 경우의 수는 모두 1이다.

   -> DP[0][1 ~ K] = 1

 

2. K개의 숫자로 N을 만드는 경우의 수는 K-1개의 숫자로 0 ~ N을 만드는 경우의 수의 합과 같다.

예를 들면,

N=1,K=1 -> DP[1][1] = DP[1][0] + DP[0][0] = 1      (모든 경우> 1)

N=1,K=2 -> DP[1][2] = DP[1][1] + DP[0][1] = 2      (모든 경우> 0 + 1, 1 + 0)

.

.

.

N=2,K=1 -> DP[2][1] = DP[2][0] + DP[1][0] + DP[0][0] = 1  (모든 경우> 2)

N=2,K=2 -> DP[2][2] = DP[2][1] + DP[1][1] + DP[0][1] = 3  (모든 경우> 2 + 0, 1 + 1, 0 + 2)

 

따라서 점화식은 다음과 같다.

DP[n][k] = DP[n][k-1] + DP[n-1][k-1] + ... + DP[1][k-1] + DP[0][k-1]
           = ∑ DP[m][k-1]  (단, 0 <= m <= n)

코드로 구현하면 아래와 같다.

#include <iostream>

using namespace std;

//d[1][1] = d[0][0], d[1][2] = d[1][1] + d[0][1], ...
//d[2][1] = d[0][0], d[2][2] = d[2][1] + d[1][1] + d[0][1], ...


int N, K;
int d[201][201];
const int MOD = 1e9;

void dp() {
	//초기값
	for (int i = 0; i < K; i++) {
		d[0][i] = 1;
	}

	//i는 만들고자 하는 수
    //j는 사용한 숫자의 개수
    //k는 i ~ 0까지의 수
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= K; j++) {
			for (int k = i; k >= 0; k--) {
            	//두 값 모두 1e9보다 작으므로 모듈러 연산을 취하지 않고 
                //더한 후 모듈러 연산을 취해도 괜찮다.
				d[i][j] += d[k][j - 1];
				d[i][j] %= MOD;
			}
		}
	}

	cout << d[N][K];
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> N >> K;
	dp();
	return 0;
}

메모리: 2180 kb

시간: 12 ms