[python/파이썬] 백준 2407 조합

문제

nCm을 출력한다.

입력

n과 m이 주어진다. (5 ≤ n ≤ 100, 5 ≤ m ≤ 100, m ≤ n)

출력

nCm을 출력한다.

예제 입력 1 복사

100 6

예제 출력 1 복사

1192052400

 

[소스 코드]

 

백준 모음집 dp 카테고리에 있는 문제지만 dp가 아닌 방법밖에 떠오르지 않아 쉬운 방법으로 풀었다.

찾아보니 dp로 풀려면 파스칼의 삼각형을 이용해야 한다고 한다.

 

팩토리얼을 import math 해서 math.factorial(n) 해도 되지만 함수로 직접 구현해서 풀어보았다.

 

1! 과 0! 은 1이므로 예외 처리해주고 나머지는 n*(n-1)! 을 반환해준다 

후에 조합 공식을 이용하여 출력하면 된다.

def fa(n): #팩토리얼 함수
    if n==0 or n==1:
        return 1
    else:
        return n * fa(n-1)

#입력 n, m
n,m = map(int, input().split())

#출력
print(fa(n)//(fa(n-m)*fa(m))) #nCm = n!/(n-m)!m!