백준 11050 이항계수 (Python)

문제 링크

문제

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

입력

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

출력

(𝑁𝐾)\(\binom{N}{K}\)를 출력한다.

---

아이디어

1. 재귀를 사용해서 수학 공식에 맞게 팩토리얼을 계산하여 풀었다.
2. fact 배열에 미리 값을 메모해놔서 같은 값을 두번 계산하지는 않게 최적화하였다.

---

제출 코드

 def solution():
    N, K = map(int, input().split())
    fact = [1, 1, 2, 6]

    def getFact(value):
        if len(fact) - 1 >= value:
            return fact[value]
        else:
            return getFact(value - 1) * value

    print(int(getFact(N) / (getFact(K) * getFact(N - K))))


solution()