[백준] 11050번 이항 계수 1 - Python

문제

자연수 N과 정수 K가 주어졌을 때 이항 계수 $\begin{pmatrix}n\\k\end{pmatrix}$를 구하는 프로그램을작성하시오

입력

첫째 줄에 $N$과 $K$가 주어진다. $(1≤N≤10,$ $0≤K≤N)$

출력

$\begin{pmatrix}n\\k\end{pmatrix}$를 출력한다.

문제에 대한 이해!

이항 계수란...

이항 계수(Binomial Cofficient) 는 이항식을 이항 정리로 전개했을 떄 각 항의 계수를 말하며, 순서가 없는 주어진 크기의 조합의 가짓수이다.

이항식 은 항이 두 개인 식의 거듭제곱(e.g. $(x+y)^2$)을 의미하고, 그런 이항식을 전개하는 것을 이항 정리 라고 한다.

정리하자면, 거듭제곱 $(1 + x) ^ n$을 이항정리했을 때, $x^k$의 계수를 말한다.

한 번, 예제를 풀어보자

예제 입력 1

5 2

예제 출력 1

10

$(1+x)^5 = x^5 + 5x^4 + 10x^3 + 10x^2 + 5x + 1$

따라서, 10x^2이기 때문에 10이라는 결과를 얻을 수 있는 것을 볼 수 있다. 하지만, 항상 이렇게 모든 식을 전개해서 찾을 수 없기 때문에 파스칼의 삼각형을 사용해서 한 번 보겠다.

이렇게, 파스칼의 삼각형을 통해서도 확인해볼 수 있었다. 이를 수식화해보자.

답안지

정답 1

위에서 구한 수식을 바탕으로 Python으로 코드를 만들어보자.

import math

n, k = map(int, input().split())

print(math.factorial(n) // ((math.factorial(k)) * math.factorial(n - k)))

정답 2

조합 $C$를 python의 itertools 모듈을 사용하여 이항 계수를 구하는 코드를 만들어보자.

from itertools import combinations

n, k = map(int, input().split())

combi = len(list(combinations(range(n), k)))

print(combi)

참고하면 좋은 블로그