[파이썬 알고리즘 문제풀이] - Section6 / 완전탐색 (백트랙킹, 상태트리와 CUT EDGE)-DFS(깊이우선탐색)기초 - 7

🚀 동전교환

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

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

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

▣ 입력예제 1
3
1 2 5
15

▣ 출력예제 1
3

import sys
# sys.stdin = open("input.text", "rt")

N = int(input())
data = list(map(int, input().split()))
M = int(input())

res = 2424242424
data.sort(reverse = True)

def DFS(L, sum):
    global res
    if L > res:
        return
    if sum > M:
        return
    if sum == M:
        if L < res:
            res = L
    else:
        for i in range(N):  #동전 하나씩 사용하면서 확인해봐야겠다
            DFS(L+1, sum + data[i])

DFS(0,0)
print(res)

🚀 코멘트

각각의 DFS는 동전의 개수만큼(N) 가지를 뻗는다.
레벨 L이 동전의 개수를 의미해 !

계속 가지를 뻗어나간다고 생각하기 !!!

이 문제에서 생각했어야 할 것은 이전까지는 레벨(인덱스)이 종료조건이었다면 이 문제는 합!을 기준으로 종료조건을 생각했어야 했어.

• 또한 이전에도 생각했던 Cut Edge를 잘 생각해야 한다!

🎃 Cut Edge를 할 때 '최솟값'에 집중해보면 L이 개수인 것을 알고 접근했어. 이미 res에 최솟값이 등록되어 있는데 계속 뻗어나갈 때 L이 res보다 커지면 더 가지를 뻗어나갈 필요가 없잖아.

• DFS로 문제를 풀때는 항상 Cut Edge 생각해야해

동전의 개수가 최소여야 하므로 들어오는 동전 값들을 내림차순으로 정렬해서 확인하는게 좋겠다.

🎃 역시 이 경우도 !! 동전의 개수만큼 반복문을 돌아서 해당 동전을 사용해서 거스름돈과 비교해야 겠구나.. 를 생각할 수 있었어야 했다.