[Algorithm] 동전교환 (DFS)

## 동전교환

# L = 동전 사용 개수

def DFS(L, sum):
    global res

    if L > res:  # cut edge
        return

    if sum > m:
        return

    if sum == m:
        if L < res:
            res = L
    else:
        for i in range(len(coin)):
            DFS(L+1, sum+coin[i])


n = int(input())
coin = list(map(int, input().split()))
m = int(input())
res = 2147000000  # 최소를 받을 변수
coin.sort(reverse=True)  # 내림차순
DFS(0, 0)
print(res)

오름차순으로 하면, 1+1+1+1... = 15 로 동전의 개수 15개까지 깊이탐색이 이루어져야 하지만

내림차순으로 정렬하면, 5+5+5 = 15 로 동전의 개수 3개를 먼저 구할 수 있다.

동전의 개수가 최소일 때를 구해야 하니 내림차순으로 정렬하는 것이 효율적이다.