8031 : 동전 조합 II
•시간제한: 3.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
$N$종류의 동전이 주어집니다. 동전들의 가치 합이 정확히 $X$가 되는 경우의 수를 구하는 프로그램을 작성하시오. 단, 순서가 달라도 사용한 동전들의 조합이 같으면 같은 경우로 취급합니다. (예를 들어, 동전 가치가 $2, 3, 5$이고 목표 합이 $9$일 때 $[2, 2, 5]$와 $[2, 5, 2]$는 같은 조합이므로 1가지 경우로만 셉니다.)
[제약 조건]
• $1 \le N \le 100$
• $1 \le X \le 10^6$
• $1 \le c_i \le 10^6$ (모든 동전 가치는 서로 다름)
[제약 조건]
• $1 \le N \le 100$
• $1 \le X \le 10^6$
• $1 \le c_i \le 10^6$ (모든 동전 가치는 서로 다름)
입력 설명
첫째 줄에 동전의 종류 $N$과 목표 합 $X$가 공백으로 구분되어 주어집니다. ($1 \le N \le 100$, $1 \le X \le 10^6$)
둘째 줄에 각 동전의 가치 $c_1, c_2, \ldots, c_N$이 공백으로 구분되어 주어집니다. 모든 동전의 가치는 서로 다릅니다. ($1 \le c_i \le 10^6$)
둘째 줄에 각 동전의 가치 $c_1, c_2, \ldots, c_N$이 공백으로 구분되어 주어집니다. 모든 동전의 가치는 서로 다릅니다. ($1 \le c_i \le 10^6$)
출력 설명
조합의 합이 $X$가 되는 경우의 수를 $10^9+7$로 나눈 나머지를 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
3 9
2 3 5
출력 예시
COPY
복사되었습니다!
복사되었습니다!
3도움
순서가 없는 조합을 구하기 위해서는 동전을 하나씩 차례대로만 고려해야 합니다. 이를 위해 바깥쪽 루프를 동전 종류로 두고, 안쪽 루프를 목표 가치 $i$로 설정합니다. 즉, 각 동전 $c$에 대해 가치 $i$를 $c$부터 $X$까지 진행하며 $dp[i] = (dp[i] + dp[i-c]) \pmod{10^9+7}$로 업데이트합니다. ($dp[0]=1$)