이항계수1

https://www.acmicpc.net/problem/11050
처음 문제를 봤을때 엄청 간단할 것 같았다. 문제는 단순하게 이항 계수를 구하는 문제이다. 그런데 수학에 손을 안대본지가 15년이 넘어가니 이항계수가 뭐였는지도 기억이 나지 않았다. 그래서 이 문제를 풀기전에 이항 계수가 뭐였는지 부터 공부를 하였다. 그런데 공부하다 보니 슬프게도 이항 계수를 이해할려면 Combination에 대해서도 알아야 하였다. 분명 많이 봤었는데 기억이 나지가 않았었다.

Combination

서로 다른 n개의 중, r개를 선택하는 경우의 수.
(단 순서는 상관안한다.)

조합을 공부하다보니 위와 같이 nCr 로 표현할수 있다. 저 값을 구할려면 !(factorial)가 붙어 있는 수를 구해야된다. 이걸 알게 되니 팩토리얼은 또 뭐였더라 라는 생각을 하게 되었다.

Factorial

1부터 어떤 양의 정수 n까지의 정수를 모두 곱한 것을 말하며 n!로 나타낸다. 0!=1로 약속하고, n이 대단히 큰 경우 스털링의 공식을 써서 근삿값을 구할 수 있다.

로 정의 할수 있다. 이걸 Python 코드로 표현을 하면 아래와 같이 제귀함수를 이용하여 표현할 수 있다.예를 들어 factorial(3)을 실행하면 아래와 같이 실행이 된다.n! = n x (n-1) x (n-2) x (n-3) ... x 1로 정의할 수 있다. 그렇다면 이번 문제도 위에 내용을 이용하면 이항계수를 쉽게 구할수 있다.

정답

import sys

# factorial을 구하는 함수.
def factorial(n):
    if n == 0:
        return 1
    return n * factorial(n-1)

N, K = map(int, sys.stdin.readline().split())

# nCr을 구하는 식
dap = factorial(N) / (factorial(N-K)*factorial(K))
print(int(dap))

마무리

알고나면 쉽게 구할수 있는 문제였다. 하지만 수학적인 내용이 잘기억이 안나서 이러한 부분을 다시 학습하는데 시간이 오래 걸린 문제였다. 진짜 수학을 안한지가 오래 되서 그런지 이런 단순한 수학적인 부분도 해매게 되는 것 같다.