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

(문제) 동전교환 (DFS)

---

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

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

입력설명

첫 번째 줄에는 동전의 종류개수 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

---

해결방법

1. 동전들을 저장하는 coins라는 리스트를 생성해 동전들을 넣는다.
2. m이라는 변수에 지불해야할 값을 할당한다.
3. coins 리스트를 정렬을 내림차순으로 한다.
4. coins의 몇개의 요소를 이용했는지를 저장할 res 변수를 생성하여 int형 변수 가장 큰 수 2147000000 값을 할당한다.
5. dfs를 이용하여 깊이 x와 coins안에 있는 동전의 합을 더 할 sum이라는 매개변수를 이용하여 함수를 작성한다.
6. 만약 깊이 x(깊이면 지금 더한 동전의 개수가 된다)가 res 보다 크거나 같을 경우 return을 시킨다. (구하는 값은 최소의 값이기 때문에 재귀함수를 끝내기 위해 return 한다)
7. sum의 값과 m이라는 값이 비교하여 만약 sum이 더 클 경우 조건에 만족하지 못하므로 return 시켜 재귀를 끝낸다.
8. sum의 값과 m의 같이 같을 경우 res변수에 현재 깊이 x, 즉 동전의 개수를 넣는다.
9. 그렇지 않을 경우, dfs 함수를 실행한다. 이때 x의 값은 +1 하고, sum은 sum = sum + coins[i]를 이용하여 sum의 값을 더한다.
10. 자식 node는 n개가 될 것이기 때문에 n번 반복한다.

---

코드

def dfs(x, sum):
    global res
    if x >= res:
        return
    if sum > m:
        return
    if sum == m:
        res = x
    else:
        for i in range(n):
            dfs(x+1, sum+coins[i])

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

# 반대로 정렬 시켜 놓아야 큰 것 부터 처리를 해서
# 동전의 최소 개수를 빨리 구할 수 있으며
# 재귀함수를 적게 돌 수 있다.
coins.sort(reverse=True)

res = 2147000000

dfs(0, 0)
print(res)