파이썬 알고리즘-79 (DP) 동전 교환

79.동전교환
다음과 같이 여러 단위의 동전들이 주어져 있을때 거스름돈을 가장 적은 수의 동전으로 교환해 주려면 어떻게 주면 되는가? 각 단위의 동전은 무한정 쓸 수 있다.

▣ 입력설명
첫 번째 줄에는 동전의 종류개수 N(1<=N<=100)이 주어진다. 두 번째 줄에는 N개의 동전의 종류가 주어지고, 그 다음줄에 거슬러 줄 금액 M(1<=M<=10,000)이 주어진다. 각 동전의 종류는 100원을 넘지 않는다.

▣ 출력설명
첫 번째 줄에 거슬러 줄 동전의 최소개수를 출력한다.

▣ 입력예제 1
3
1 2 5
15

▣ 출력예제 1
3

설명 : 5 5 5 동전 3개로 거슬러 줄 수 있다.

내 코드

n=int(input())
lst=list(map(int, input().split()))
m=int(input())

dy=[int(1e10)]*(m+1)
dy[0]=0
for i in lst:
    for j in range(i,m+1):
        # 복잡하게 몫과 나머지를 구할 필요 없이 dy에서 동전 값만 빼줬어도 풀 수 있는 문제
        # min메소드를 사용하면 한 줄에 끝낼 수 있다
        if (j//i+dy[j%i])<dy[j]:
            dy[j]=j//i+dy[j%i]
print(dy[-1])

이전의 가방 문제와 동일한 방식이므로 같은 논리로 풀었다. 하지만 코드에 개선의 여지가 많이 있다.

풀이

if __name__=="__main__":
    n=int(input())
    coin=list(map(int, input().split()))
    m=int(input())
    dy=[1000]*(m+1);
    dy[0]=0
    for i in range(n):
        for j in range(coin[i], m+1):
            dy[j]=min(dy[j], dy[j-coin[i]]+1)
    print(dy[m])

반성점

• 코드를 간결하게 작성하지 못했다.

배운 것