취미로 코딩하기

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

이번에 볼 문제는 백준 17213번 문제인 과일 서리이다.
문제는 아래 링크를 확인하자.

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

$N$개의 과일 각각을 적어도 하나씩은 훔쳐야하므로 이를 미리 하나씩 훔쳤다고 생각하면 구하고자하는 값은 $N$가지 과일 가운데 $M-N$개의 과일을 (중복을 허용하여) 고르는 경우의 수와 같게 된다. 이는 $N-1$개의 막대기와 $M-N$개의 과일을 나열하는 경우의 수와 같게 볼 수 있다.

파스칼의 삼각형을 이용해 위의 경우의 수를 계산하고 이를 출력해 문제를 해결하자.

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

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

ll comb[32][32];
void combinit() {
	comb[0][0] = 1;
	for (int n = 1; n < 32; n++) {
		comb[n][0] = 1;
		for (int r = 1; r <= n; r++) comb[n][r] = comb[n - 1][r - 1] + comb[n - 1][r];
	}
}

int N, M;

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

	combinit();

	cin >> N >> M;
	cout << comb[M - 1][N - 1];
}