[백준] 11050 이항 계수 1

문제

자연수(N)와 정수(K)가 주어졌을 때 이항 계수 $\binom{N}{K}$를 구하는 프로그램을 작성하시오.

입력

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

출력

$\binom{N}{K}$를 출력한다.

내 풀이

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

answer = 1
for i in range(1, n+1):
    answer *= i

for i in range(1, k+1):
    answer /= i
    
for i in range(1, n-k+1):
    answer /= i

print(int(answer))

코멘트

문제 자체는 쉽지만 이항 계수의 개념을 잊어버려서 (...) 정리하고자 포스팅.
이항 계수란, 주어진 집합에서 원하는 개수만큼 순서 없이 뽑는 조합의 개수를 의미하는데, $\binom{N}{K}$와 같이 표기한다. $\binom{N}{K}$는 N개 중에서 K개를 순서 상관 없이 뽑는 조합의 수를 의미하는 것이다. 이항 계수 공식은 아래와 같다.
$\binom{N}{K} = \frac{n!}{k!(n-k)!}$

이는 순열과 조합 중 "조합"과 같은 개념이다. 순열과 조합도 헷갈리니까 정리하고 넘어가자...
순열 $_n{P}_k$ (Permutations)은 n개 중에서 k개를 순서를 고려하여 뽑는 경우의 수를 의미한다. 예를 들어 list1 = [1, 2, 3, 4]라는 배열에서, 3개(1, 2, 4)를 뽑는다고 했을 때, 순서를 고려하기 때문에 (1, 2, 4), (1, 4, 2), (2, 1, 4), (2, 4, 1), (4, 1, 2), (4, 2, 1)이 모두 다른 경우로 취급되어 경우의 수가 더 많아진다. 순열의 개수는 아래의 공식으로 계산할 수 있다.
$_n{P}_k = \frac{n!}{(n-k)!}$

파이썬에서 사용할 때에는 itertools 라이브러리의 permutations 함수를 쓰면 된다.

from itertools import permutations

list1 = [1, 2, 3, 4]
list2 = list(permutations(list1, 2))

print(list2)
# [(1, 2), (1, 3), (1, 4), (2, 1), (2, 3), (2, 4), (3, 1), (3, 2), (3, 4), (4, 1), (4, 2), (4, 3)]

조합 $_n{C}_k$ (Combinations)은 n개 중에서 k개를 순서를 고려하지 않고 뽑는 경우의 수를 의미한다. 예를 들어 list1 = [1, 2, 3, 4]라는 배열에서, 3개(1, 2, 4)를 뽑는다고 했을 때, 순서가 상관없기 때문에 (1, 2, 4)와 (1, 4, 2)는 같은 경우로 취급되어 경우의 수가 순열보다 적다. 조합의 개수는 아래의 공식으로 계산할 수 있다.
$_n{C}_k = \frac{n!}{k!(n-k)!}$

파이썬에서 사용할 때에는 itertools 라이브러리의 combinations 함수를 쓰면 된다.

from itertools import combinations

list1 = [1, 2, 3, 4]
list2 = list(combinations(list1, 2))

print(list2)
#[(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)]

References

https://www.acmicpc.net/problem/11050
https://velog.io/@falling_star3/파이썬-순열-조합-중복순열-중복조합itertools를-활용한-구현