백준 17213.과일 서리

Silver2 문제
17213.과일 서리

처음에는 '쉽군 ㅋㅋ' 하면서 함수를 만들어 풀었는데 시간초과가 되었다 ㅜㅜ

from itertools import combinations
n=int(input())
m=int(input())
nums=list(range(n))
ans=[]
answer=0
def back(start):
    global answer
    if len(ans)==m-n:
        answer+=1
        return
    for i in range(start,n):
        ans.append(i)
        back(i)
        ans.pop()
back(0)
print(answer)

중복조합 공식을 이용해서 풀어야 했다.
n : 선택지의 개수
k : 중복을 허용해서 선택할 개수, 여기서는 m에서 과일종류수를 뺀 나머지

nHk = (k+n-1)!/k!(n-1)!

정답코드는

import math
n=int(input())
m=int(input())
nums=list(range(n))
ans=[]
answer=0
a = math.factorial(n+(m-n)-1)
b = math.factorial(m-n) * math.factorial(n-1)
print(a//b)