동전 교환 (Cut Edge Tech)

인프런 김태원님의 파이썬 알고리즘 문제풀이를 듣고 작성한 글입니다.

https://inf.run/Wa5t

파이썬 알고리즘 문제풀이 (코딩테스트 대비) - 인프런 | 강의

 

#강의 풀이
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+a[i])

if __name__ == "__main__":
    n = int(input())
    a = list(map(int, input().split()))
    m = int(input())
    res = 2147000000
    a.sort(reverse=True)
    DFS(0, 0)
    print(res)

 

DFS를 L = level과 sum으로 진행

DFS( L ) 에서 L의 값이 동전의 갯수라고 볼수있다.

 

시간을 단축하는 cut edge

1. a 배열을 내림차순 sort하여 값이 큰 동전부터 체크한다.

2. L의 최솟값 res보다 커지는 순간 return 한다.

3. 동전의 합 sum이 m보다 커지는 순간 return 한다.

4. 같을때는 L이 최소라면 DFS 순환 후 res 출력