μ΄ν κ³μ λ΄ λ§λλ‘ μ 리(with μ¬κ·)
0. μ΄νκ³μλ? binomial coefficient?
μ£Όμ΄μ§ ν¬κΈ°μ (μμ μλ) μ‘°ν©μ κ°μ§μ. nκ°μ μμλ₯Ό κ°μ§λ μ§ν©μμ ν¬κΈ°κ° r μΈ λΆλΆμ§ν©μ κ³ λ₯΄λ κ²½μ°μ μ.
λ³΄ν΅ μμ μκ³Ό κ°μ΄ κ³μ°νλ€.
1. μ¬κ·λ‘ 보λ μ΄νκ³μ
μ΄νκ³μλ μ νμμΌλ‘ ꡬν μλ μλ€.
(νμ€μΉΌμ μΌκ°νμ κ°μ΄ 보면 μμμ μ΄ν΄νκΈ° μ½λ€)
#include <stdio.h>
long long bc(int n, int c) {
if (n == c || c == 0) return 1;
else return bc(n - 1, c) + bc(n - 1, c - 1);
}
int main(void) {
int n, c;
scanf("%d %d", &n, &c);
printf("%lld\n", bc(n, c));
}
μμ μμ μ¬κ·λ‘ νννλ€.
κ·Έλ°λ° μ΄λ κ² μ§λ©΄ λ¬Έμ μ μ΄ μκΈ°λλ°, μ‘°κΈλ§ ν° μλ₯Ό λ£μ΄λ κ³μ°μ΄ νμ°ν λλ €μ§λ€λ κ²μ΄λ€. μλνλ©΄, μ΄ κ²½μ° μ€λ³΅ν΄μ κ³μ°νλ λΆλΆμ΄ κΈ°νκΈμμ μΌλ‘ λμ΄λλ€. μλ νΈμΆ νΈλ¦¬λ₯Ό 보μ.
λ λ² μ΄μ κ³μ°νλ λΆλΆμ νμκΉλ‘ μΉ ν΄ λ³΄μλ€. κ·ΈλΌ, μ΄λ° μ€λ³΅ κ³μ°μ μμ κΈ° μν΄ λ¬΄μμ ν μ μμκΉ?
2. λ©λͺ¨μ΄μ μ΄μ
κ²°κ΅ μμ μ κ³μ°μ ν λ²λ§ νλ κ²μ΄λ€. κ·Έλ λ€λ©΄, ν λ² κ³μ°λ κ²°κ³Ό κ°μ μ΄λκ°μ μ μ₯ν΄λκ³ , λ€μ κ·Έ κ°μ μ΄λ€λ©΄ μ΄λ¨κΉ? μ΄λ₯Ό μν κΈ°λ²μ΄ λ©λͺ¨μ΄μ μ΄μ μ΄λ€.
μλλ λ©λͺ¨μ΄μ μ΄μ μ μ΄μ©ν΄μ μ§ μ΄νκ³μ μ½λλ€.
long long memo[200][200] = { 0, };
long long bc_memo(int n, int r) {
if (memo[n][r] > 0)return memo[n][r];
if (n == r || r == 0) return memo[n][r] = 1;
else return bc_memo(n - 1, r) + bc_memo(n - 1, r - 1);
}
int main(void) {
int n, r;
scanf("%d %d", &n, &r);
printf("%lld\n", bc_memo(n, r));
}
μ, λ©λͺ¨μ΄μ μ΄μ μ μ¬μ©νμ§ μμλλΌλ©΄ 20 C 10μ κ³μ°ν λ νΈμΆμ΄ 369511λ² κ±Έλ¦¬μ§λ§, μμ μ½λλ₯Ό μ¬μ©νλ€λ©΄ 201λ²μΌλ‘ νκΈ°μ μΌλ‘ νΈμΆ νμλ₯Ό μ€μΌ μ μλ€.
reference
https://ko.wikipedia.org/wiki/%EC%9D%B4%ED%95%AD_%EA%B3%84%EC%88%98
λ¬Έμ λ‘ νμ΄λ³΄λ μκ³ λ¦¬μ¦(ν©μΈμ±, κΉμ©ν)