[백준🥈3] #2407 조합 (Python)(Math/DP)

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

2407번: 조합

 

문제

nCm을 출력한다.

입력

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

출력

nCm을 출력한다.

예제 입력 1

100 6

예제 출력 1

1192052400

 

✔️ Code 1 (math의 factorial 사용)

import math

n, m = map(int, input().split())
up = math.factorial(n)
down = math.factorial(m) * math.factorial(n-m)

print(up//down)

 

✏️ Comment

조합 공식 이용

 

 

✔️ Code 2 (DP)

n, m = map(int, input().split())

dp = [[0 for i in range(101)] for j in range(101)]

for i in range(1, 101):
    dp[i][0] = 1
    dp[i][i] = 1

for i in range(2, 101):
    for j in range(1, i):
        dp[i][j] = dp[i-1][j-1] + dp[i-1][j]

print(dp[n][m])

 

✏️ Comment

아직 DP는 어려운 듯.. 구글링 코드 참고했다. 규칙만 잘 찾으면 쉬운데 규칙 찾는 게 어렵다. 특히 수포자에겐(...)