[알고리즘] 이항 계수

이항계수에 대해 알아보자.

 

 

이항계수란?

이항식을 이항정리 했을 때의 각 항의 계수

ex.

(x+y)² = x² + 2xy + y²                    => 1 2 1

(x+y)³ = x³ + 3x²y + 3xy² + y³     => 1 3 3 1

 

 

이항계수 구하기

(x+y)ⁿ 의 k번째 항의 계수 =  ₙCₖ (n = 자연수, 0 ≤ k ≤ n)

(x+y)ⁿ 의 k번째 항의 계수는

으로 나타낸다.

이유는 다음과 같다.

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))

 

 

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

11050번: 이항 계수 1