2225번 합분해

 

불러오는 중입니다...

상당히 간단한 풀이의 문제였다.

 

일단 N과 K를 아무 숫자나 정하고 차근차근 세어보기로 한다.

 

(10,K)로 대충 정해보자

 

N=10 K=1: 1개

N=10 K=2 : (0,10), (1,9), (2,8) ... (10,0) 11개

N=10 K=3 : (0,0,10), (0,1,9) ... (0,10,0) / (1,0,9), (1,1,8) ... (1,9,0) / ..... / (10,0,0)

 

N=10 K=3에서 붉은 색 부분을 보자. N=10 K=2일 때의 경우의 수 그대로다.

주황 색 부분은? N=9 K=2일 때의 경우의 수이다.

쭉 진행해보면 마지막 파란색 부분은 N=0 K=2일 때의 경우의 수다.

 

간단하게 점화식을 얻을 수 있다.

 

(N,K)=(N,K-1)+(N-1,K-1)+.....+(0,K-1) 

 

#include <iostream>
using namespace std;

int N, K;
long long int DP[201][201];
int main() {
	cin >> N >> K;
	for (int i = 0; i <= N; i++) {
		DP[i][1] = 1;
	}
	for (int i = 1; i <= K; i++) {
		DP[0][i] = 1;
	}

	for (int i = 1; i <= N; i++) {
		for (int j = 2; j <= K; j++) {
			for (int k = 0; k <= i; k++) {
				DP[i][j] += DP[i - k][j - 1]%1000000000;
			}
		}
	}
	cout << DP[N][K]%1000000000;
	return 0;
}