[백준] 2225 합분해

문제

0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구하는 프로그램을 작성하시오.

덧셈의 순서가 바뀐 경우는 다른 경우로 센다(1+2와 2+1은 서로 다른 경우). 또한 한 개의 수를 여러 번 쓸 수도 있다.

입력

첫째 줄에 두 정수 N(1 ≤ N ≤ 200), K(1 ≤ K ≤ 200)가 주어진다.

출력

첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다.

 

DP문제입니다.

테이블을 계속 작성하다보면 규칙이 보입니다.

 

dp[1][1~N] 와 dp[1~K][0]을 1로 초기화하고,

dp[2~K][1~K]를 dp[i][j]=dp[i-1][j]+dp[i][j-1]로 정리하면 정답입니다.

 

이때 모듈러 1000000000를 구해야하는데,

a=b+c일때 모듈러K는

a=((b%K)+(c%K))%K 로 구할 수 있습니다.

#include<bits/stdc++.h>
#define FAST ios_base::sync_with_stdio(false),cin.tie(NULL);
#define mset(v) memset(v,0,sizeof(v));
#define rep(i,a) for(int i=0;i<a;++i)
#define REP(i,a) for(int i=1;i<=a;++i)

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef tuple<int, int, int>ti;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
int dy[] = { -1,0,1,0 }, dx[] = { 0,1,0,-1 }, INF = 987654321;

ll N, K, dp[202][202];
int main() {
	FAST;
	cin >> N >> K;
	REP(i, N)dp[1][i] = 1;
	REP(i, K)dp[i][0] = 1;
	for (int i = 2; i <= K; i++) {
		REP(j, N) {
			dp[i][j] = (dp[i - 1][j] % 1000000000 + dp[i][j - 1] % 1000000000)%1000000000;
		}
	}
	cout << dp[K][N]%1000000000;
}