[C++] BOJ(백준) 2225 합분해

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

2225번: 합분해

 

DP 문제다.

 

처음 생각한 방법은 2차원 배열을 이용해

1을 포함해 1개로 n을 만드는 경우의 수	2를 포함해 1개로 n을 만드는 경우의 수	...
1을 포함해 2개로 n을 만드는 경우의 수	2를 포함해 2개로 n을 만드는 경우의 수	...
...	...	...

이렇게 배열 자체를 n을 구하기 위한 경우의 수를 구하려 했다.

겹치는 부분을 생각할 수도 없고 규칙도 찾기 어려워 버렸다.

 

두 번째 생각한 방법은 모든 경우의 수를 다 적고 거기에서 규칙적인 변화를 찾았다.

작은 규칙을 찾긴 했지만 사용할 수 있는 방법이 없고, 중복되는 숫자가 가능하다 보니 너무 복잡해서 또 버렸다.

 

세 번째 방법은 위의 방법에서 방향을 틀어 경우의 수 규칙을 찾았다.

[n][k] 배열로 나타내면 아래의 표처럼 나타난다.

1	2	3	4
1	3	6	10
1	4	10	20
1	5	15	35
1	6	21	56
1	7	28	84

여기서 찾을 수 있는 규칙은 [n][k]를 구하기 위해서는 [n-1][k]와 [n][k-1]의 합을 구해야 한다는 점이다.

즉, 점화식은 dp[n][k] = dp[n-1][k] + dp[n][k-1]이다.

 

#include <iostream>
using namespace std;

int dp[201][201];

int main() {
	int n, k;	cin >> n >> k;

	for (int i = 1; i <= k; i++) dp[1][i] = i;

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

	cout << dp[n][k];
}

DP답게 코드는 간단하다.

규칙 찾고 점화식까지 구했는데 n, k가 헷갈려서 배열 구성하는데 꽤 걸렸다...;;