접근
https://www.acmicpc.net/problem/2294
전형적인 DP 문제여서 점화식을 파악하는 과정이 중요했다. 이전 단계인 2293번 '동전 1' 문제를 풀고오면 조금 수월하게 접근할 수 있는것 같다.
합이 K 일 때, 사용한 동전의 최소 개수를 구하기 위하여, 합이 i 일 때 사용한 최소 동전의 개수를 구하는 작은 문제로 쪼개었다.
- DP 배열을 K + 1 의 길이로 생성하고, DP[i]의 의미를 합이 i 일 때 사용한 최소 동전의 개수를 계산하여 갱신한다.
- 갱신이 완료된 후, DP[K]의 값을 표시하고, 합을 K로 만들 수 없다면 -1을 출력한다.
가치가 i 인 동전을 사용할 때, 가치의 합이 j 인 칸을 갱신하기 위해서는 j - i 칸에 해당하는 동전의 갯수에 1을 더하거나(i 동전이 한개 더 사용되므로), 혹은 기존에 j 칸에 있던 값 중 작은 값으로 갱신하면 된다.
갱신할 때 작은 값이 사용되기 때문에 초기 값을 INF 로 두고, 갱신을 마친 후 DP[K] 값이 INF 라면 -1을 출력하면 된다.
코드
import sys
input = sys.stdin.readline
INF = float("inf")
N, K = map(int, input().split())
coinValue = [int(input()) for _ in range(N)]
dp = [INF] * (K + 1)
dp[0] = 0
for i in coinValue:
for j in range(i, K + 1):
if j - i >= 0:
dp[j] = min(dp[j - i] + 1, dp[j])
print(dp[K] if dp[K] != INF else -1)
더 생각해 볼 것?
가치가 같은 동전이 여러번 주어질 수 있지만, 각각의 동전은 몇개라도 사용될 수 있기 때문에, 여러번 주어지는 것을 모두 입력하여 배열에 넣을 필요는 없다. 중복되는 코인을 삭제하면 순회가 줄어들기 때문에 시간을 줄일 수 있을 것이다. 백준에는 해당 과정을 추가하여 시간을 절약했지만, 간단한 과정이기 때문에 본문에는 추가하지 않았다.
코드나 내용 관련 조언, 부족한 점 및 질문 언제든 환영합니다!
반응형
'코딩 > 백준 (Python)' 카테고리의 다른 글
백준 10815: 숫자 카드 (Python) (0) | 2023.04.15 |
---|---|
백준 2193: 이친수 (Python) (0) | 2023.04.15 |
백준 2458: 키 순서 (Python, PyPy) (1) | 2022.09.23 |
백준 2616번: 소형기관차 (Python) (0) | 2022.09.21 |
백준 3020번: 개똥벌레 (Python) (0) | 2022.09.21 |
최근댓글