[伯俊][Python][Greedy]コイン0

📃 質問する

ジュンギュが持っているコインは全部でN種類で、どれもたくさんあります.
硬貨を適当に使って、その価値の和をKにします.必要なコインの数の最大値を求めるプログラムを作成してください.
入力
第1行はNとKを与える.(1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000)
2行目から、N行目では昇順にコインの価値Aiが与えられる.(1≦Ai≦100000,A 1=1,i≧2の場合、AiはAi-1の倍数)
しゅつりょく
Kドルを作るのに必要なコインの数の最大値を1行目に出力します.

💻 問題を解く

""" Code1 """
# time : 20

n, k = map(int, input().split())
coin_types = []
for i in range(n):
    coin_types.append(int(input()))

result = 0
coin_types.sort(reverse=True)      
for i in range(n):
    result += k // coin_types[i]
    k %= coin_types[i]

print(result)

""" Code2 """
# time : 7

n, k = map(int, input().split())
coin_types = []
for i in range(n):
    coin_types.append(int(input()))

result = 0
for i in range(n):
    coin = coin_types.pop()         
    result += k // coin
    k %= coin

print(result)

""" Code3 """
# time : 1

n, k = map(int, input().split())
coin_types = []
for i in range(n):
    coin_types.append(int(input()))

result = 0
coin_types.reverse()               
for i in range(n):
    result += k // coin_types[i]
    k %= coin_types[i]

print(result)

キー(Key)

2番目に入力した値(コインの種類)から最後の値(=大きい値)を取得します.

「硬貨個数の最高額」を求めたいので、とりあえず大額で計算.

時間を比較すると、Code3が一番早いです.

Code1銀sort()なので時間が一番長いようです.

・Code2・もしlist.pop()だったらリストの最後の値が出てきます.これは事件を解決しないで、最後のお金を抽出する方法です.

・Code3使用list.reverse()単純に並べ替えを覆す.
コインの種類を昇順で入力していない場合は使うべきsort(reverse=True)、質問では昇順で入力しているのでsort()簡単に入力するだけreverse()