[DFS기초] - 동전교환

동전교환  

 

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

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

 

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

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

 

▣ 입력예제 1

3
1 2 5
15

▣ 출력예제 1

3

 

설명 : 5 5 5 동전 3개로 거슬러 줄 수 있다.

 

 

나의 코드

def DFS(L,summ):
    if summ==m:
        print(L)
        return
    else:
        for i in range(n):
            DFS(L+1,summ+arr[i])


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

Minn=500

arr.sort(reverse=True)
DFS(0,0)

출력값을 찾은 코드이긴한데 그냥 이문제는 풀지 못한 코드이다..

조금만 입력값이 커져도 time-out이다..

 

cut-edge를 위해 arr을 내림차순으로 정렬한 뒤 탐색을 한것 말곤 다른 추가적인  방법이 떠오르지 않는다...!ㅠㅠ

 

 

 

 

정답 코드

import sys
sys.stdin=open("input.txt", "r")
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)

if L>=res:
        return
if sum>m:
    return

위와 같은 2개의 cut-edge가 추가 되었다.

첫 번째는 이미 가장 작은 레벨(가짓수)를 구해서 그 이후 더 많은 레벨을 가진 값들은 고려할 필요가 없다.

두번째는 거슬러줄 금액보다 큰 금액은 고려하지 않아도 되기 때문이다.