[파이썬] 11050번: 이항 계수 1

11050번: 이항 계수 1 (acmicpc.net)

11050번: 이항 계수 1

이항계수 공식을 알고 팩토리얼을 구현할 수 있다면 풀 수 있는 문제이다.

이항계수 공식은 다음과 같다. 

출처: Binomial Coefficient Calculator (omnicalculator.com)

입력의 범위가 1부터 10으로 아주 작기 때문에 이 문제에서는 팩토리얼을 직접 구현하여 풀어도 무방하다.

하지만 범위가 말도 안되게 커진다면 말이 달라지는데, 이 때의 이항 계수 알고리즘은 아래 블로그를 참조하는 것을 추천한다. (나도 더 공부해야지...) 

[조합론] 이항계수 알고리즘 3가지 - Parkito's on the way (shoark7.github.io) 

[조합론] 이항계수 알고리즘 3가지

 

팩토리얼 구현 코드

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

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

ans = factorial(n) // (factorial(n-k) * factorial(k))
print(ans)