1. (x+y)ⁿ 를 이항정리 한다고 할때, 모든 항은 총 n개의 x, y로 이뤄져있다. ex. xⁿ, xⁿ⁻¹y, ... , xyⁿ⁻¹, yⁿ => 0번째 항은 x: n개, 첫 번째 항은 x: (n-1)개, y: 1개로 총 n개
2. 즉, (x+y)(x+y)(x+y)...(x+y) 에서 n개의 x, y를 중복 없이 선택한 경우의 수가 각 항의 계수가 될 수 있다. ex. (x+y)(x+y) => x를 두 개 선택하는 경우: 1개, x와 y를 각각 하나씩 선택하는 경우: 2개, y를 두개 선택하는 경우: 1개 ∴ x² + 2xy + y²
3. k번째 항의 y의 차수는 k이므로 n개의 (x+y)에서 y를 중복 없이 k개 선택한 경우의 수가 계수가 된다. ∴ (x+y)ⁿ 의 k번째 항의 계수 = ₙCₖ (n = 자연수, 0 ≤ k ≤ n)
적용
이제 백준 11050번: 이항 계수 1 문제를 풀어보자.
문제
자연수 N과 정수 K가 주어졌을 때 이항 계수를 구하는 문제이다.
풀이
풀이 1. ₙCₖ를 출력하면 된다.
import sys
n, k = map(int, sys.stdin.readline().split())
def factorial(x):
if x == 0 or x == 1: return 1
else: return x * factorial(x-1)
print(factorial(n)//(factorial(k)*factorial(n-k))) #ₙCₖ
풀이 2. 거슬러 올라가며 윗 노드들을 더해주는 방법이다.
import sys
def bc(n, k):
if k == 0 or k == n: return 1
else: return bc(n-1, k-1) + bc(n-1, k)
n, k = map(int, sys.stdin.readline().split())
print(bc(n, k))
