[백준 2407번] 조합 - python

2407번

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

문제

nCm을 출력한다.

입력

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

출력

nCm을 출력한다.

🐰 나의 코드

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

nsum=1

m=min(m,n-m)

for ni in range(n,n-m,-1):
    nsum*=ni
    
for mi in range(1,m+1):
    nsum//=mi
    
print(nsum)

수험생 시절에 열심히 하던 조합을 다시 만났다.

나이스 투 믿유..^^

nCm의 공식은 n! / (m! x (n-m)!)인데, 이걸 최대한 단순화해야겠다는 생각을 갖고 있었다.

그러다 기억한 공식을 따라서 코드를 작성했다.

예를 들어 8C5라면 8C3과 결과가 같은데,

이렇게 되면 (8*7*6)/(3*2*1)을 하면 공식과 같은 결과를 더 빠르게 구할 수 있다.

이걸 이용해서 코드를 짰다.

우선 입력받은 두 숫자를 n,m에 저장하고 출력될 nsum을 1로 저장했다.

m은 더 작은 수를 해야 더 빨리 계산을 할 수 있을 것 같아 min을 이용하여 m과 n-m 중에서 더 작은 수로 저장했다.

for문은 우선 n에서 n-m+1까지 구할 수 있도록 했고, 

이렇게 구해진 i는 nsum에 곱해지도록 했다.

다음 for문에선 1부터 m까지 mi를 구하는데, 이 mi를 nsum에서 나누도록 했다.

최종적으로 nsum은 nCm의 결과값을 같기 때문에 그대로 출력했다.