[파이썬(python)] 이것이 취업을 위한 코딩테스트다 효율적인 화폐 구성

오랜만에 다이나믹 프로그래밍

 

엇!

답이 맞는줄 알았는데 잘보니 틀리다.

won[i]는 i원을 만들 수 있는 코인의 최소 개수를 저장해야하는데,

아래의 경우... 최소 개수를 저장하지 않는다는 문제가 있다.

초기화할때 -1로 모두 저장해버려서 최소값을 저장하게 되면 그냥 -1이 저장되기 때문이다..

 

import sys

n, m = map(int, sys.stdin.readline().rstrip().split())
coin = []
coin.sort()
for _ in range(n):
    coin.append(int(sys.stdin.readline().rstrip()))

won = [-1] * (m+1)

for i in coin:
    if i <= m:
        won[i] = 1

for i in range(m+1):
    if won[i] == 1:
        continue

    for j in coin:
        if 0 <= i-j <= m:
            if won[i-j] != -1:
                won[i] = won[i-j] + 1
                #이부분이 과연 won[i]값에 최소 화폐의 개수가 저장되는지 의구심이 듬..

print(won[m])

 

그래서

초기화 할 때

불가능한 큰 값으로 저장해줘야한다.

이렇게 하니까 정답!

 

import sys
n, m = map(int, sys.stdin.readline().rstrip().split())
coin = []

for _ in range(n):
    coin.append(int(sys.stdin.readline().rstrip()))

coin.sort()

won = [10000] * (m+1)

for i in coin:
    if i <= m:
        won[i] = 1

for i in range(m+1):
    if won[i] != 10000:
        continue
    
    for j in coin:
        if 0 <= i-j <= m:
            if won[i-j] != 10000:
                won[i] = min(won[i-j]+1, won[i])

if d[m] == 10000:
    print(-1)
else:
    print(d[m])