[백준 11050] 이항 계수 1 Python

이항 계수 1

• 티어 : Bronze 1
• 시간 제한 : 1 초
• 메모리 제한 : 256 MB
• 알고리즘 분류 : 수학, 구현, 조합론

문제

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

입력

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

출력

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

예제 입출력

---

이항 계수(Binomial Coefficient)
조합론에서 등장하는 개념으로 주어진 크기 집합에서 원하는 개수만큼 순서 없이 뽑는 조합의 가짓수

Algorithm

1. N * ... * 1을 총 K번 진행
2. K! 계산
3. 1번의 결과를 2번의 결과로 나눔

Code

# Factorial 계산하는 함수
def factorial(K):
    if K < 2:
        return 1
    else:
        return K * factorial(K-1)
    
# 입력
N, K = map(int, input().split())

# N * N-1 * ...
num1 = 1
for i in range(K):
    num1 *= N-i

# K!
num2 = factorial(K)

# N * N-1 * ... // K!
print(num1 // num2)

메모리: 30864 KB
시간: 72 ms