⚡️algorithm
[DP] 백준 2294. 동전2 - ing
남남이루
2022. 4. 19. 09:52
주어진 동전들로 k원 금액을 만들어라!
틀린 이유
1. for 문 구현에서 index랑 범위 설정이 이해가 잘 안 갔었다. << 결정적
(보충)
2. n과 k를 헷갈려해서 d[k] = k원에 해당하는 동전개수 가 아니라 d[n]을 출력함
n, k = map(int, input().split())
coins = list(int(input()) for _ in range(n))
d = [10001] * (k+1)
d[0] = 0
for c in coins:
for i in range(c, k+1):
d[i] = min(d[i-c] + 1, d[i])
if d[k] == 10001:
print(-1)
else:
print(d[k])
인덱스가 너무나 이해가 안갔었다.
DP 초보인 나를 너무나 괴롭게 했던 문제,
종일 낑낑 거리다가 다른 문제(카드 구매하기) 풀고 다시 푸니까 이제 좀 알겠다. 혼자 힘으로 다시 풀 수 있어야 되겠다. 특히 왜 이중 for문이 쓰이고, 인덱스 관계랑, for문의 범위지정 에 관한 부분이 제일 까다로웠다.