백준 BOJ 2225 - 합분해

오늘 학원에서 써먹은 개념을 그대로 쓸수 있었던 문제

nHr 중복조합을 구현하면 되는 문제이다.

 

0<=x 들을 K개 더해서 N를 만드는 nHr의 기본 형태이다

nHr = (n+r-1)C(r) 임을 이용하면 되는데,

구현은 워낙 간단한 DP여서 생략하도록 하겠다.

 

www.acmicpc.net/problem/2225

2225번: 합분해

#include <bits/stdc++.h>
#define MOD 1000000000
using namespace std;

int dp[512][512] = {0};

int nCr(int n, int r){
	if(n==r) return dp[n][r] = 1;
	if(r==0) return dp[n][r] = 1;
	
	if(dp[n][r] != 0) return dp[n][r] % MOD;
	return dp[n][r] = (nCr(n-1,r-1) + nCr(n-1,r)) % MOD;
}

int main(){
	int n,r;
	scanf("%d %d", &n, &r);
	nCr(n+r-1, r-1);
	printf("%d", dp[n+r-1][r-1] % MOD);
	return 0;
}