[python] 백준 11050 : 이항 계수

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

11050번: 이항 계수 1

분류 : 수학, 구현, 조합론

---

이항 계수 : n개의 서로다른 것들 중에서 k개를 선택하는 조합의 경우의 수

 

n = 5, k = 2일때를 예로들면

[1, 2, 3, 4, 5] 에서 2개를 뽑는 조합의 수가 몇개인지를 구하는 것이다.

(조합 : 순서를 생각하지 않고 뽑는 경우의 수)

여기서는 (1, 2), (1, 3), (1, 4), (1, 5), (2, 3), (2, 4), (2, 5), (3, 4), (3, 5), (4, 5) => 총 10개가 되겠다.

 

1 : combinations 함수를 이용한 풀이

from itertools import combinations
N, K = map(int, input().split())
lst = [i for i in range(N)]
print(len(list(combinations(lst, K))))

 

combinations(iterable객체, r개)
iterable 객체 : 반복문, 리스트 등 반복 가능한 객체
r개 : 해당 객체에서 중복을 허용하지 않고 뽑을 개수(생략 안됨)
뽑는 순서를 고려하지 않는다. -> (AB와 BA를 같은 것으로 본다.)

 

---

2 : 팩토리얼을 이용한 풀이

팩토리얼은 재귀함수를 이용해서 구현할 수 있다.

def factorial(n):
    if n == 0:
        return 1
    return n * factorial(n-1)

n, k = map(int, input().split())
print(factorial(n) // (factorial(k) * factorial(n - k)))

 

최초의 인자값에서 1을 감소시킨 값을 같은 함수에 연쇄적으로 발생시키게 하면서

factorial(5) = 5x4x3x2x1과 같은 방식으로 표현된다.