7104 : 경우의 수 — 동전
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
K가지 종류의 동전이 있습니다. 각 동전은 무한히 사용할 수 있습니다.
이 동전들을 사용하여 목표 금액 T원을 만드는 서로 다른 방법의 수를 구하는 프로그램을 작성하십시오.
동전의 구성 순서만 다른 것은 같은 방법으로 취급합니다.
[제약 조건]
• 각 동전 값은 10,000 이하의 자연수입니다
이 동전들을 사용하여 목표 금액 T원을 만드는 서로 다른 방법의 수를 구하는 프로그램을 작성하십시오.
동전의 구성 순서만 다른 것은 같은 방법으로 취급합니다.
[제약 조건]
• 각 동전 값은 10,000 이하의 자연수입니다
입력 설명
첫째 줄에 동전의 종류 수 K와 목표 금액 T가 공백으로 구분되어 주어집니다. (1 ≤ K ≤ 100, 1 ≤ T ≤ 10,000)
둘째 줄에 각 동전의 액면가 K개가 공백으로 구분되어 오름차순으로 주어집니다. 각 동전 값은 10,000 이하의 자연수입니다.
둘째 줄에 각 동전의 액면가 K개가 공백으로 구분되어 오름차순으로 주어집니다. 각 동전 값은 10,000 이하의 자연수입니다.
출력 설명
동전들을 사용하여 T원을 만드는 방법의 수를
1,000,000,007로 나눈 나머지를 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
3 10
1 2 5
출력 예시
COPY
복사되었습니다!
복사되었습니다!
10도움
냅색 형태의 동적 계획법(DP)을 사용합니다.
dp[i] = dp[i] + dp[i - coin] 관계식을 활용하십시오.