[DP] 동전 교환 - 가짓수

문제

$K$가지 동전을 무한히 써서 금액 $M$을 만드는 방법의 수를 구하라. 동전을 고른 묶음이 같으면 같은 방법으로 본다(순서는 구분하지 않는다). 답이 클 수 있으니 $1{,}000{,}000{,}007$로 나눈 나머지를 출력한다.

접근

동전을 바깥 반복문에, 금액을 안쪽 반복문에 두면 순서 구분 없이 조합만 센다.

$dp[m] \mathrel{+}= dp[m - c] \quad (\text{동전 } c \text{마다}, \; m = c \ldots M), \quad dp[0] = 1$

바깥과 안쪽 반복문 순서를 바꾸면 순열(순서 구분)을 세게 되니 주의한다.

입출력 예시

입력:
3 5
1 2 5
출력: 4