# Adding Ways

# 문제

 

# 입력 및 출력

 

# 풀이

dp[i][j] = dp[i-1][j-1] + dp[i-j][j]

점화식은 위와 같다.

왜 이렇게 되는지 예를 들어 설명해보자

 

예) (n, k) = (5, 3) 일 때 5를 3개의 자연수로 나타내는 방법은

1. 1이 들어가는 경우

2. 1이 들어가지 않는 경우

이렇게 나눌 수 있다.

 

1이 들어가는 경우엔  1 + (4를 2개의 자연수로 나타내는 방법) 이 되기 때문에 dp[i-1][j-1] 식이 오게 된다.

1이 들어가지 않는 경우엔 j가지 방법으로 나눌 때 1은 무조건 하나씩 기본으로 놓고, 최소 2가 되어야 하기 때문에

1씩 주고 남은 i-j개를 j가지로 나누어주면 된다.

 

#include <fstream>
#define MOD 1000000007;
using namespace std;

ifstream fin("addingways.inp");
ofstream fout("addingways.out");
int dp[301][21];

void make_dp() {
	for (int i = 1; i <= 300; i++) {
		for (int j = 1; j <= 20; j++) {
			if (j > i) break;
			if (j == 1 || j == i) dp[i][j] = 1;
			else dp[i][j] = (dp[i - 1][j - 1] + dp[i - j][j]) % MOD;
		}
	}
}

int main() {
	int n, k;
	make_dp();
	while (1) {
		fin >> n >> k;
		if (!n && !k) break;
		fout << dp[n][k] << "\n";
	}
}

 

헷갈려서 분할관련 블로그를 참고했다.

https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=vollollov&logNo=220989048062 

자연수의 분할 P(n, k)