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

문제링크: https://www.acmicpc.net/problem/2225

2225번: 합분해

 

생각하는 과정이 필요한 문제였습니다. 각각의 결과값들을 순차대로 구하다 보면 규칙을 찾을 수 있습니다.

점화식만 구하면 쉽게 구현할 수 있는 문제였습니다.

 

n = 5 k = 4 의 예제를 살펴보겠습니다.

 

표	0	1	2	3	4	5
dp[1]	0	0	0	0	0	1
dp[2]	1	1	1	1	1	1
dp[3]	6	5	4	3	2	1
dp[4]	21	15	10	6	3	1

dp[k]은 dp[k][0] ~ dp[k][n]의 합이 됩니다. 그리고 각각의 dp[k][i] 는 dp[k-1][i] ~ dp[k-1][n] 까지의 합이 됩니다. 

비교적 쉽게 점화식을 구할 수 있습니다. 

 

그래서 ex) 5 4의 결과값은 21+15+10+6+3+1 = ? 이 되겠죠 ㅎㅎ

 

 

 

 

 

 

그다음으로 주의하셔야 할 것은 %연산을 해주는 위치와 숫자 범위입니다. 매번 dp[k-1][i] ~ dp[k-1][n] 의 연산마다 %1000000000연산을 해줘도 해당문제에서는 상관없습니다. 하지만 조금더 컴팩트 하게 코딩하기 위해서 dp[k][i] 에서만 %1000000000연산을 해주고 싶었습니다. 

 

근데 만약 dp[k-1] 의 합이 다 10^9를 초과해서 오버플로우가 난다면, 에러가 날 수 밖에 없습니다. 그래서 long long 을 사용해서 배열을 구현했습니다.

 

 

 

아래는 정답코드입니다. :) 직접 표를 작성해보시고 점화식을 시그마형태로 구하고 구현해보세요! 화이팅

 

#include <iostream>
using namespace std;
long long dp[202][202] = { 0 };
int n, k;
long long result = 0;

int main() {
	cin >> n >> k;
	dp[1][n] = 1; // 초기값 설정
	for (int i = 1; i <= k; i++) {		
		for (int j = 0; j <= n; j++) {
			for (int u = j; u <= n; u++)
				dp[i][j] += dp[i - 1][u];
			dp[i][j] %= 1000000000;
		}
	}
	
	for (int i = 0; i <= n; i++)
		result += dp[k][i];
	result %= 1000000000;
	cout << result << endl;
}