8030 : 동전 조합 I
•시간제한: 3.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
$N$종류의 동전이 주어집니다. 동전들의 가치 합이 정확히 $X$가 되는 경우의 수를 구하는 프로그램을 작성하시오. 단, 동전의 순서가 다르면 다른 경우로 취급합니다. (예를 들어, 동전 가치가 $2, 3, 5$이고 목표 합이 $9$일 때 $[2, 2, 5]$와 $[2, 5, 2]$는 서로 다른 경우입니다.)
[제약 조건]
• $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
복사되었습니다!
복사되었습니다!
8도움
동전의 순서가 유의미하므로, $dp[i]$를 합이 $i$가 되는 경우의 수라고 하면 $dp[i] = \sum_{c} dp[i-c]$ (단, $i-c \ge 0$, $dp[0]=1$) 식을 적용할 수 있습니다. 가치 $i$를 $1$부터 $X$까지 순차적으로 구하며 각 동전들을 대입하는 $O(N \times X)$ 점화식으로 해결 가능합니다.