[solved.ad 실버3] 2407_조합 (파이썬, DP)

제한 사항

 

문제

nCm을 출력한다.

입력

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

출력

nCm을 출력한다.

예제

---

나의 풀이

문제에서 조합을 설명해주지 않아서 조합 구하는 식에 대해 찾아봤다 (까묵...)

나는 위 식을 살짝 변형해 사용했다.

n, m = map(int, input().split())
ja, mo = 1, 1
for i in range(1, m):
    ja *= (n-i)
    mo *= i
ja *= n
mo *= m
print(ja//mo)

분자, 분모 각각 반복문을 돌릴 수도 있었지만 범위가 거의 유사했기 때문에 한 번의 반복만 하기 위해서

분자에서는 n을 제외한 (n-1)(n-1) ... (n-(r-1)) 까지 계산했고,

분모에서는 r을 제외한 1*2*...*(r-1) 까지 계산했다. 둘 다 1~(r-1)까지 반복하는 부분이 겹친다. (문제에서는 r이 아니라 m)

이후 분자에 n을 곱하고, 분모에는 r을 곱해주어서 분자와 분모를 구했고, 나눠서 답을 만들었다.

 

만약 파이썬이 아닌 다른 언어를 사용한다면 반복문 중간에 분자와 분모를 나눠주면서 오버플로우가 나지 않도록 하면 될 것이다.

 

채점 결과