Python3でまったり競技プログラミング 1日目（貪欲法）

プログラミング最近全然やってなかったのでリハビリ。1週間続くかな。続くといいな。

実践的プログラミングの資料から適当に抜粋してやっていこうと思う。

Make Purse Light | Aizu Online Judge

coin = [10,50,100,500,999999]
J = True
while True:
    n = int(input())
    if n == 0:
        break
    else:
        if not J:
            print()
        else:
            J = False
        L = list(map(int,input().split()))
        S = 10*L[0]+50*L[1]+100*L[2]+500*L[3]
        res = S-n #とりあえず硬貨を全部使ったものと仮定する
        change = [res%coin[i+1]//coin[i] for i in range(4)] #ここでお釣りとしてどの硬貨が何枚戻ってくるかを計算している
        
        for i in range(4):
            if change[i] < L[i]: #お釣りとして戻ってくる枚数の方が少なければ採用
                print(coin[i],L[i]-change[I])

最初、各硬貨は20枚までと決まってるし全探索すれば（1ケースあたり20**4通り）まあいけるやろ〜〜〜なんて安易に考えてたら普通に通りませんでした。

というか普通に発想自体難しくてワロタよ
日本の硬貨は、それより小さい金額のお金が大きい金額を割り切るという特質があるため、「大きい金額で払えるならばできるだけ支払った方が得（枚数が少なくて済む）」という戦略が取れます。そうでない場合は違う戦略をとる必要が出てくる。

※通らなかったコード　供養

while True:
    n = int(input())
    if n == 0:
        break
    else:
        L = list(map(int,input().split()))
        S = sum(L)
        ans = float('inf')
        coin = [10,50,100,500]
        for i in range(21):
            for j in range(21):
                for k in range(21):
                    for l in range(21):
                        if i <= L[0] and j <= L[1] and k <= L[2] and l <= L[3]:
                            t = i*10+j*50+k*100+l*500
                            if n-t > 0:
                                None
                            elif n-t == 0:
                                ans = S-(i+j+k+l)
                                p = [i,j,k,l]
                            else:
                                cur = S-(i+j+k+l)
                                z = t-n
                                cur += z//500
                                z = z-(z//500)*500
                                cur += z//100
                                z = z-(z//100)*100
                                cur += z//50
                                z = z-(z//50)*50
                                cur += z//10
                                if cur < ans:
                                    ans = cur
                                    p = [i,j,k,l]
        for a in range(4):
            if p[a] != 0:
                print(coin[a],p[a])
        print()