[DP] 백준 2294. 동전2 - ing

주어진 동전들로 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문의 범위지정 에 관한 부분이 제일 까다로웠다.