[백준] 17213번 - 과일 서리 (파이썬) (feat. 중복조합 공식)

1. 문제

 

2. 코드

n = int(input())
m = int(input())

temp = m - n
za = 1
mo = 1


for i in range(1, temp+n):
    za *= i

for i in range(1, temp+1):
    mo *= i
for i in range(1, n):
    mo *= i
    

print(int(za/mo))

 

 

3. 풀이

중복조합을 이용하는 문제.

중복조합 공식은 아래와 같다.

출처 : 네이버 지식백과

여기에서 n은 선택지의 개수를, k는 중복을 허용하여 선택할 개수를 의미한다.

예를 들어 3개 중 4개를 중복을 허용하여 뽑는다면 3H4이다.

nHk = (k + n-1)! / k!(n-1)! 이다.

3H4 = 6! / 4!2! = 15가 된다.

 

참조 사이트는 https://kenadams.tistory.com/65 이다.