졍's 기술 블로그

이항 계수 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