취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 13707번 문제인 합분해 2이다.

문제는 아래 링크를 확인하자.

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

이 문제는 대표적인 중복조합 예제이다.

양의 정수 N을 음이 아닌 K개의 정수의 합으로 나타내는 경우의 수는 N+K-1 choose N 과 같다.

파스칼의 삼각형을 계산해 문제를 해결해주자. 높이 10000짜리 파스칼의 삼각형은 주어진 문제의 메모리제약 내로 만들 수 있고, 시간 또한 사칙연산의 반복이므로 크게 부족하지 않다.

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;
typedef long long ll;

int comb[10001][10001]; //comb[n][r] = nCr

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	for (int n = 0; n < 10001; n++) comb[n][0] = 1;
	for (int n = 1; n < 10001; n++) {
		for (int r = 1; r <= n; r++) {
			comb[n][r] = (comb[n - 1][r - 1] + comb[n - 1][r]) % 1000000000;
		}
	}
	int N, K; cin >> N >> K;

	cout << comb[N + K - 1][N];
}