[DP] 백준 2225 합분해 C++

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

2225번: 합분해

---

---

풀이 :

0 부터 N 까지 숫자 중 K개의 합이 N이 되는 경우의 수를 구하는 문제

dp인건 알겠는데 막상 풀려면 조금 막막하다. 숫자가 작은 경우 부터 생각하고 초깃값 설정과 점화식도출이 초점을 맞춰서 풀어보자!

우선 N이 값이 얼마든 한개를 뽑아서(K=1) N이 되게하는 경우? 당연히 1가지이다.(해당 숫자 N을 뽑으면 됨) 그다음 부터가 중요한데 작은 숫자부터 차근히 생각해 보자

내가 생각하는 가장 직관적인 풀이는 dp[K][N] = 0~N까지 K개의 수를 뽑아 합이 N이 되게하는 경우의 수

일때, dp[K][N] = dp[K][N-1]+dp[K][N-1] 이식은 테이블로 보면 K =3, N=3 일때

index	1	2	3	4
1
2			dp[k-1][n]
3		dp[k][n-1]	(k=3, n=3)
4

이런 규칙성을 띄는데 잘생각해보면 직관적으로 답을 얻을 수 있다 위에서 가정한 3,3을 예로들면

dp[3][3] = dp[2][3] + dp[3][2]

이렇게 나타낼 수 있는데 가정한 점화식을 풀어서 생각해보자

dp[2][3] = 0~3 까지의 수 중 2개의 수를 뽑아 합이 3이 되는 경우의 수 = 4가지

dp[3][2] = 0~2 까지의 수 중 3개의 수를 뽑아 합이 2가 되는 경우의 수 = 6가지

더해서 총 10가진데 왜 더하는 이유?

4가지 뒤에 0 붙으면 3개 뽑아 합이 3인 경우 4가지,

6가지 뒤에 1 더하면 3개 뽑아 합이 3인 경우 6가지 

 

 

코드 :

#include <iostream>
#define ll long long
#define mod 1000000000
using namespace std;

ll dp[202][202];
int n, k;
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n >> k;

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

	for (int K = 2; K <= k; K++) {
		for (int N = 0; N <= n; N++) {
			dp[K][N] = (dp[K][N - 1] + dp[K - 1][N]) % mod;
		}
	}

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

}