[Baekjoon/Python] 이항 계수(11050)

문제

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

 

이항 계수란

• 조합론에서 등장하는 개념으로 주어진 크기 집합에서 원하는 개수만큼 순서없이 뽑는 조합의 가짓수를 일컫는다.
• 하나의 아이템에서 "뽑거나", "안뽑거나" 두 가지 선택이 있기 때문에 "이항"이라는 말이 붙었다.

 

이항 계수의 정의

• 전체 집합에서 원소의 개수 n에 대해 k개의 아이템을 뽑는 이항 계수는 다음과 같이 정의한다.

ex) 원소 개수 6개에 대해 2개의 아이템을 뽑는 이항계수는?

- 6! / 4! / 2! = 720 / 24 / 2 = 15, 즉 15가 된다.

 

 

이항 계수의 성질

• 2번, n개 중에서 k를 선택하는 것은 선택하지 않은 나머지 (n-k)개를 선택하는 것과 같다.
• 3번, 이항 계수 정의를 유도하면 3번식 도출할 수 있다.
• 4번, 파스칼 삼각형과 관련이 있다.

 

풀이

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

• 만약 n이나 k가 0이란 값이 들어가 0!이라면 1을 반환해야 하기 때문에 0일 때 1을 return한다.
• 그 다음, 이항 계수 정의에서 설명하였듯이 팩토리얼을 사용해여 해당 값을 구한다.