Algorithm - 동전교환(냅색 알고리즘)

 

알고리즘 입문 수업을 듣고 중요한 내용을 정리했습니다.
개인 공부 후 자료를 남기기 위한 목적이므로 내용 상에 오류가 있을 수 있습니다.

 

문제

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

 

여러 단위의 동전들이 주어져 있을 때, 거스름돈을 가장 적은 수의 동전으로 교환해주는 프로그램을 작성하시오.

단, 각 단위의 동전은 무한정 사용할 수 있다.

 

 

*입력 설명

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

두 번째 줄에는 N개의 동전 종류가 주어진다.

세 번째 줄에는 거슬러 줄 금액 M(1 ≤ M ≤ 500)이 주어진다.

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

 

*출력 설명

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

 

 

---

 

 

풀이(Python)

답안

import sys
sys.stdin = open('AA/input_81.txt', 'rt')

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])
    
# 출력 : 3

 

input_81.txt(입력)

3
1 2 5
15

 

 

중요내용

1. 리스트 dy에는 거슬러주는데 사용된 동전의 최소개수를 저장한다.
2. 즉, dy[j]에 j원을 거슬러주는데 사용된 동전의 최소개수를 저장하는 것이다.
3. 변수 coin에는 동전의 종류를 저장한다.
4. dy에는 동전의 최소개수를 저장하기 때문에 초기값으로 충분히 큰 수인 1000을 미리 저장해둔다. (최소개수를 구하는 문제)
5. dy[0] = 0으로 초기값을 미리 설정한 이유는 0원을 거슬러주는데 사용되는 동전의 개수는 0개이기 때문이다.
6. for j in range(coin[i], m+1): 에서 반복문이 1이 아닌 coin[i] 부터 시작하는 이유는 coin[i]의 동전을 추가할 때 해당 동전보다 작은 단위의 동전은 고려할 필요가 없기 때문이다.
7. dy[j] = min(dy[j], dy[j-coin[i]]+1)는 기존의 최소 동전 개수와 coin[i] 동전을 추가로 사용할 경우 새롭게 얻는 최소 동전의 개수를 비교하여 더 작은 값을 dy[j]에 저장해주는 코드이다.