[백준]11050_이항계수1, 11051_이항계수2

https://www.acmicpc.net/problem/11050
이항 계수 ${\binom{n}{k}}$를 구하기

https://www.acmicpc.net/problem/11051
이항 계수 ${\binom{n}{k}}$를 10,007로 나눈 나머지를 구하기

Solved

✔ 참고: 마크다운 문법으로 수식 쓰기

✔ 이항계수? ${\binom{n}{k}}$ = ${_nC_k}$ = $\frac{n!}{(n-k)!k!}$

✔ 이항계수 알고리즘 3가지
중요한 이항계수 성질은 다음과 같다.
1. $\binom{n}{k}$ = ${_nC_k}$ = $\frac{n!}{(n-k)!k!}$
2. $\binom{n}{k}$ = $\binom{n}{n-k}$
3. $\binom{n}{k}$ = $\binom{n-1}{k}$ + $\binom{n-1}{k-1}$
4. $\sum_{k=1}^N\binom{n}{k}=2^n$
✨ (3)은 DP, (4)는 파스칼의 삼각형과 관련이 깊다.

11050_이항계수1 풀이

1. $\binom{n}{k}$ = ${_nC_k}$ = $\frac{n!}{(n-k)!k!}$ = $\frac{n*…*(n-k)}{(n-k)!}$ 이용

using namespace std;
#include <iostream>

int main() {
	int n, k;
	cin >> n >> k;
	if (k == 0) {
		cout << "1\n";
		return 0;
	}
	int p = 1, q = 1;
	int answer = 1;
	for (int i = 1, j=n; i <= k; i++, j--) {
		answer *= j;
		answer /= i;
	}
	cout << answer << '\n';
	return 0;
}

11051_이항계수2 풀이

곱으로 구한다면 수가 너무 커지니 DP를 사용하자.

using namespace std;
#include <iostream>
#include <cstring>

int dp[1001][1001];

int solve(int n, int k) {
	if (n == k || k == 0) return dp[n][k] = 1;
	if (n < k) return 0;
	if (n < 0 || 1000 < n || k < 0 || 1000 < k) return 0;
	if (dp[n][k] != -1) return dp[n][k];

	return dp[n][k] = (solve(n - 1, k - 1) + solve(n - 1, k)) % 10007;
}

int main() {
	int n, k;
	cin >> n >> k;
	memset(dp, -1, sizeof(dp));
	solve(n, k);
	cout << dp[n][k] << '\n';
	return 0;
}