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

문제

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

 

 

 

풀이

• 답안 : Python

import sys
input = sys.stdin.readline

def DFS(L, sum):
    global res
    
    # CUT EDGE
    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+a[i])

n = int(input())
a = list(map(int, input().split()))
a.sort(reverse=True)
m = int(input())
res = 1e9

DFS(0, 0)
print(res)

- 상태트리가 여러 가지로 뻗어있는 문제 (DFS 사용)

 

- n (동전 종류 개수), a(동전 종류 별로 담긴 리스트), m(거슬러 줄 금액)

- a.sort(reverse=True) → 제일 큰 수부터 확인하는 것이 효율적

- res → 최소 동전 개수 (때문에 제일 큰 값으로 초기화 해준다.)

- DFS(L, sum) → L (레벨 = 동전 개수), sum (거슬러 줄 금액과 비교)

 

- 거슬러 줄 금액과 비교했을 때, 거슬러줄 금액을 넘었을 때 return 해준다.

- 거슬러 줄 금액과 일치할 때, 계산한 동전의 개수가 res보다 작다면 res값을 변경해준다.

- 만약 거슬러 줄 금액과 일치하지 않을 때, n만큼 for문을 돌려준다.

   DFS(L+1, sum+a[i]) → 레벨 1 증가, 거슬러 줄 금액에 a[i]를 더해준다.

 

- CUT EDGE) if L > res:

   이미 답이 L로 나왔는데, L이 res보다 큰 경우까지 계산하지 않기 위해서

   (= 이미 레벨이 L에서 끝났는데 더 깊이 있는 것들까지 계산할 필요가 없음)