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이 바로 동전을 사용한 개수이다 !!

結局時間に制限されて...
40分...

先生コード

じかんせいげんかいていほう
先に並べ替えて、大きい数から前に並べます
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이 바로 동전을 사용한 개수이다 !!