BOJ | 2407 - 조합 (python)

🧮 조합

 

 

 

---

✏️ 문제

nCm을 출력한다.

 

입력

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

 

출력

nCm을 출력한다.

 

 

---

💡 해결방법

nCm = n*(n-1)*(n-2)*・・・*1 / m*(m-1)*(m-2)*・・・*1 임을 이용해 구할 수 있다.

처음에 n/m * (n-1)/(m-1) ~ 이렇게 곱해나가는 방식으로 구하려고 했지만 큰 수로 간다면 오차가 있을 수 있다.

 

그러기 때문에 위의 식에서 분자 부분인 n*(n-1)*(n-2)*・・・*1 과

분모 부분인 m*(m-1)*(m-2)*・・・*1 을 따로따로 계산한 후, 마지막에 두 수를 나눠준 값을 출력했다.

 

 

👩🏻‍💻 소스코드

import sys
input = sys.stdin.readline
n, m = map(int, input().split())
d = [[1, 1] for _ in range(m+1)]
result = 0

for i in range(1, m+1):
    d[i][0] = d[i-1][0] * (n-i+1)
    d[i][1] = d[i-1][1] * i

result = (d[m][0]//d[m][1])
print(result)

 

---