8029 : 최소 동전 개수
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
$N$종류의 동전이 주어집니다. 각 동전은 무한히 많이 사용할 수 있습니다.
동전들을 적절히 조합하여 그 가치의 합이 정확히 $X$가 되도록 만들 때, 필요한 최소 동전의 개수를 구하는 프로그램을 작성하십시오.
[제약 조건]
• $1 \le N \le 100$
• $1 \le X \le 10^6$
• $1 \le c_i \le 10^6$ (각 동전의 가치)
동전들을 적절히 조합하여 그 가치의 합이 정확히 $X$가 되도록 만들 때, 필요한 최소 동전의 개수를 구하는 프로그램을 작성하십시오.
[제약 조건]
• $1 \le N \le 100$
• $1 \le X \le 10^6$
• $1 \le c_i \le 10^6$ (각 동전의 가치)
입력 설명
첫째 줄에 동전의 종류 $N$과 목표 가치 $X$가 공백으로 구분되어 주어집니다.
둘째 줄에 각 동전의 가치 $c_1, c_2, \ldots, c_N$이 공백으로 구분되어 주어집니다.
둘째 줄에 각 동전의 가치 $c_1, c_2, \ldots, c_N$이 공백으로 구분되어 주어집니다.
출력 설명
목표 가치 $X$를 만드는 데 필요한 최소 동전 개수를 출력합니다. 가치 $X$를 만들 수 없다면
-1을 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
3 11
1 5 7
출력 예시
COPY
복사되었습니다!
복사되었습니다!
3도움
$dp[i]$를 가치 $i$를 만들기 위해 필요한 최소 동전 개수라고 합시다.
초기값 $dp[0]=0$, 나머지는 $\infty$로 설정한 후 점화식 $dp[i] = \min_{c} (dp[i-c] + 1)$ (단, $i-c \ge 0$)을 적용하여 $O(N \times X)$ 시간에 해결합니다.
초기값 $dp[0]=0$, 나머지는 $\infty$로 설정한 후 점화식 $dp[i] = \min_{c} (dp[i-c] + 1)$ (단, $i-c \ge 0$)을 적용하여 $O(N \times X)$ 시간에 해결합니다.