파이썬 알고리즘 048 | 동전교환

48. 동전교환

다음과 같이 여러 단위의 동전들이 주어져 있을때 거스름돈을 가장 적은 수의 동전으로 교환
해주려면 어떻게 주면 되는가? 각 단위의 동전은 무한정 쓸 수 있다.
▣ 입력설명
첫 번째 줄에는 동전의 종류개수 N(1<=N<=12)이 주어진다. 두 번째 줄에는 N개의 동전의 종
류가 주어지고, 그 다음줄에 거슬러 줄 금액 M(1<=M<=500)이 주어진다.
각 동전의 종류는 100원을 넘지 않는다.
▣ 출력설명
첫 번째 줄에 거슬러 줄 동전의 최소개수를 출력한다.
▣ 입력예제 1
3
1 2 5
15
▣ 출력예제 1
3
설명 : 5 5 5 동전 3개로 거슬러 줄 수 있다.

<내 풀이>

def DFS(x,s):
    if s==m:
        print(x)
        sys.exit(0)
    else :
        for i in range(n) :
            DFS(x+1,s+k[i])

if __name__=='__main__' :
    n=int(input())
    k=list(map(int, input().split()))
    m=int(input())
    DFS(0,0,)
    

-1이 15개로 되는 경우만 나온다

==>다른 방법으로도 도전해봤는데 여전히 15가 나온다, 어떤 부분이 문제일까

def DFS(x):
    global min
    if x==m:
        if sum(res)==m:
            if min>x:
                min=x
        return
    else :
        for i in range(n) :
            DFS(x+1)
            res[x]=k[i]

if __name__=='__main__' :
    n=int(input())
    k=list(map(int, input().split()))
    m=int(input())
    min=900
    res=[0]*m
    DFS(0)
    print(min)
    

====>무엇이 문제였나면 입력값이 1,2,5였다
이렇게 되면 dfs가 돌 때 1부터 쭉쭉쭉 보면서 도는 것이라서 가장 처음 만나는 애가 15인 것이다 (1이 15개 인거)그래서 입력값을 반대로 해주면 5,2,1 부터 되고 가장 최소의 개수만으로 15합 달성해내는 애가 도출된다 ===> 그런데 위 코드처럼 해도 계속recursion error가 난다, 첫번째 예시입력값에서만 적용됨

<강의를 듣고 얻은 힌트로 얻은 최종풀이>

• recursion error 뜨는 것은 s==m아닌 경우에 계속 DFS반복되고 있어서임
• 따라서 s가 m넘어가는 경우는 볼 필요없으니 return해서 가지치기 해버린다

def DFS(x,s):
    if s==m:
        print(x)
        sys.exit(0)
    if s>m:
        return
    else :
        for i in range(n) :
            DFS(x+1,s+k[i])

if __name__=='__main__' :
    n=int(input())
    k=list(map(int, input().split()))
    m=int(input())
    k.sort(reverse=True)
    DFS(0,0)
    

<풀이>

• 강사님은 예시를 역순으로 취해서 처음으로 얻은 애로 구한게 아니고
• res라는 최솟값 하나 설정해두고 최솟값을 res에 갱신시켜주는 방식으로 하셨다
  if sum==m :
  if L<res:
  res=L
  이런 방법으로 하셨다

(1) - 근데 이건 시간 초과 걸린다

def DFS(L, sum):
    global res
    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)

(2) 따라서 더 뭔가를 가지쳐줘야 한다

• res는 가장 최소의 답(이 res는 DFS(x)에서 x와 동일)이다
  그래서 res보다 큰 x들은 굳이 봐줄 필요없어서 바로 컷 해버려도 된다

def DFS(L, sum):
    global res
    if sum>m:
        return
    if L>res: #이 부분만 추가해주면 시간이 엄청 줄어든다
    	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)

<반성점>

• return을 쓰면 함수 끝내고 값 내보내주는 것
• 자꾸 사소한 포인트들을 놓친다 한번 더 냉정하게 검토하는 습관을 들이자

<배운 점>

• DFS에서는 필요없는 부분은 냉정하게 CUT해서 시간을 줄이고, recursion error가 나지 않게 하는 것이 아주 중요