N,M,P = map(int,input().split())
mod = 10**9+7
def cal(N):
result = 1
for i in range(P):
result *= N-min(i,M); result %= mod
return result
combination = [1]
for i in range(P):
combination.append(combination[-1]*(N-i)//(i+1))
result = 0
for n in range(P):
result += combination[n]*cal(N-n)*(-1)**(n%2); result %= mod
print(result)조합을 이용해서 해결하였다.
사실 처음에는 "모든 노래를 플레이리스트에 추가해야 한다" 라는 말을 못봤었다.
그래서 코드의 cal 함수 자체가 정답인 줄 알았다.
cal 함수를 설명하면,
플레이리스트에 노래를 추가할 때 맨 처음에는 N개의 노래를 추가할 수 있다. 그리고 N-1개, N-2개 ... N-M개. 그러다가 M+2번째가 되면 N-M-1개가 아닌, N-M개의 노래를 추가할 수 있게 된다. (M개가 지났으므로) 이를 나타낸 함수이다.
그래서 어떻게 모든 노래를 추가할까 고민하다가 조합을 이용하면 되겠다고 생각하였다.
노래가 N개일 때, 합집합 공식에 따라서
(N개의 노래를 모두 이용하는 경우의 수) = (N개의 노래 경우의 수) - (N-1개 노래 경우의 수) * (N개의 노래 중 N-1개를 뽑는 경우의 수) + (N-2개 노래 경우의 수) * (N개의 노래 중 N-2개를 뽑는 경우의 수) -....
와 같이 된다.
따라서 N개 노래 경우의 수는 cal 함수로, 노래를 뽑는 경우의 수는 combination 리스트를 미리 만들어서 구현할 수 있었다.
참고로 이 문제는 원래는 DP로 푸는 문제인데, 내 풀이가 훨씬 빠르지만, 그래도 DP로는 어떻게 해결할 수 있는지도 고민해보아야겠다.
오늘의 교훈) DP로 해결하는 방법도 생각해보자