[백준2407&파이썬] 조합의 경우의 수를 구할때는 수학 공식을 이용하자

# 문제

백준 2407 조합 파이썬 풀이

2407번: 조합

 

# 코드

import sys

n,m = map(int,sys.stdin.readline().split())
arr = [i for i in range(1,n+1)]

# nCm
# n! / (n-r)! * r!
# DP 로 팩토리얼을 구하자

mulit = 1
cnt = 2
dp = [-1] * 101
dp[1] = 1
while True :
  if cnt == n+1 :
    break
  dp[cnt] = dp[cnt-1]*cnt
  cnt+=1

print(dp[n] // ((dp[n-m]) * dp[m]))

# math모듈을 이용해 쉽게 구할 수 있다.
import math
n, m = map(int, input().split())
print(math.comb(n, m))

 

# 풀이

• itertools를 사용하면 시간초과가 난다. 이건 모든 조합의 수를 구해버리기 때문에 조합의 수학 공식을 이용하자.
• 팩토리얼을 dp를 사용해서 쉽게 구할 수 있다.
• 한번 구해놓으면 combination(조합)을 구할때 썼던 것을 재사용 할 수 있다.
• 최대 크기가 100이기 때문에 수는 커지지만, 파이썬에서는 충분히 가능하기 때문에 풀이가 가능하다.
• 파이썬 math모듈에 조합을 구할 수 있다.