[알고리즘] 동전교환(냅색 알고리즘)

(문제) 동전교환(냅색 알고리즘)

---

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

각 단위의 동전은 무한정 쓸 수 있다.

입력설명

첫 번째 줄에는 동전의 종류개수 N(1<=N<=12)이 주어진다.

두 번째 줄에는 N개의 동전의 종류가 주어지고, 그 다음줄에 거슬러 줄 금액 M(1<=M<=500)이 주어진다.

각 동전의 종류는 100원을 넘지 않는다.

출력설명

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

테스트케이스

입력예제	출력예제
3 1 2 5 15	3
5 1 5 7 11 15 39	5
5 1 8 20 25 50 129	5
11 1 5 10 15 20 25 30 50 70 65 90 390	5
12 1 5 10 15 20 25 30 50 70 65 90 100 290	3

---

해결방법

냅색 알고리즘

1. 다이나믹 테이블 dt 생성
2. dt 값은 전부 0으로 초기화
3. 테이블 인덱스 의미는 거슬러 줄 수 있는 돈의 최소 동전의 개수

(참고)
자세한 해결 방법 참고

---

코드

n = int(input())

coins = list(map(int, input().split()))

m = int(input())

# 최대 거슬러 줄 금액 15 원을
# 최소의 동전으로 나눌 수 있는
# 거슬러 줄 금액을 작은 인덱스 영역으로 생성
# 0 원을 거슬러 줄 경우 최소의 동전 수, 1 원을 거슬러 줄 경우 최소의 동전 수 ...
# (각 인덱스가 의미하는 것 : X 원을 거슬러 줄 경우 최소의 동전 수)
dt = [0] * (m + 1)

# 가지고 있는 각 동전 종류로 최소의 동전 수로 거슬러 줄 수 있는 값을 구한다
for coin in coins:
    # 큰 기준의 거슬러 줄 경우의 동전 수를
    # 작은 기준의 거슬러 줄 경우의 동전 수를 합쳐서 결과를 도출
    for j in range(coin, m + 1):
        # 기존의 값이 만약 초기화 했을 때의 0 값이거나
        # 기존에 존재하는 거슬러주는 동전의 개수가
        # 새로운 동전의 경우와 비교하여 작으면 새로운 동전의 최소 거스름 돈전 수로 최신화 한다.
        if dt[j] == 0 or dt[j] > dt[j-coin] + 1:
            # 만약 동정 2를 이용하여 4원을 거슬러 줄 경우
            # 4원에서 2를 빼 2원을 거슬러 줄 최소의 경우를 앞에서 구했기 때문에
            # 그 값을 이용하여 자기 자신을 더하므로 dt[j-coin] + 1 이 된다
            dt[j] = dt[j-coin] + 1

print(dt[-1])