Part5.7_완전탐색_부분집합 구하기(DFS)__동전교환

내가 생각한 코드..

생각 못해서 힌트 보고 맞혔다..

import sys
sys.stdin = open("input.txt", "rt")


def DFS(L,sum):
    global cnt

    if sum == price:
        if L < cnt:
            cnt = L
 
    if sum > price:
        return
        
    else:
        for i in range(n):
            DFS(L+1, sum+a[i])


if __name__ == "__main__":
    n = int(input())
    a = list(map(int,input().split()))
    price = int(input())
    cnt=2147000000
    DFS(0,0)
    print(cnt)
    # 여기서 사용한 level이 바로 동전을 사용한 개수이다 !!

그랬더니 time Limit 걸렸다.....
40점...

선생님 코드

time limt 개선법
일단 sort 하여 큰 수부터 앞서도록 정렬 했다

a.sort(reverse=True)

만약 LEVEL이 3까지 와서 15인 수(거스를 돈의 기준 가격)가 되었는데 LEVEL 4 , 5... 까지 볼 필요가 있을까? LEVEL이 동전의 개수인걸 !!

없지 !!

최소 동전 개수를 찾는 우리는 새로운 값을 갱신할 수 있는 방법을 찾아야 한다.
그것이 바로

if L > res:
return

import sys
#sys.stdin = open("input.txt", "rt")


def DFS(L,sum):
    global cnt

    if sum == price:
        if L < cnt:
            cnt = L
    if L > cnt:
        return
    if sum > price:
        return
        
    else:
        for i in range(n):
            DFS(L+1, sum+a[i])


if __name__ == "__main__":
    n = int(input())
    a = list(map(int,input().split()))
    a.sort(reverse=True)
    price = int(input())
    cnt=2147000000
    DFS(0,0)
    print(cnt)
    # 여기서 사용한 level이 바로 동전을 사용한 개수이다 !!