백준/11050번 :: 이항계수 1 (Python, 파이썬, 알고리즘)

 

문제

---

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

 

입력

---

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

 

출력

---

 (NK)를 출력한다.

 

예제

---

예제입력

5 2

 

예제출력

10

 

코드

---

# -*- coding: utf-8 -*-
# Python 3.4.5
import sys
memo = [0] * 11
def factorial(num) :
    if num <= 1:
        memo[num] = 1
        return memo[num]
    # 이미 계산된 값
    if memo[num] != 0:
        return memo[num]
    # memoization
    memo[num] = num * factorial(num-1)
    return memo[num]
# Main
if __name__ == '__main__':
    n, k = map(int, sys.stdin.readline().split())
    print(factorial(n)//(factorial(k)*factorial(n-k)))​

 

이항계수  

(NK)

는 nCk를 뜻한다.

 

이미 계산한 팩토리얼 값은 추후에 계산하지 않도록 Memoization을 이용했다.

 

결과

---

 

※ 직접 문제 풀고 돌려본 뒤, 채점까지 마친 후에 작성한 글입니다.

더 좋은 방법이 있다면, 댓글로 알려주시면 감사하겠습니다 :)

 

문제 출처

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