[伯俊]硬貨0(11047)-python

978 ワード
白駿 アルゴリズム#アルゴリズム# コーディングテスト テキストリンク

▼▼問題


ジュンギュが持っているコインは全部で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行目に出力します.

🎈 I/O例


<入力>
10 4200
1
5
10
50
100
500
1000
5000
10000
50000
<出力>
6

👩‍💻 マイコード


この問題はグリディアルゴリズムの最も代表的な問題であるコイン問題である.そのため難易度は簡単で、すぐに問題を解くことができます.私の実現方法は以下の通りです.
  • 最も価値のあるコインを先に出して、Kより大きいならやめましょう.
  • K未満の場合は、シェアを結果に保存し、Kを硬貨で割って値に変換します.
    • N, K = map(int, input().split()) # 동전종류, 가치
coins = [] # 동전 배열
result = 0

for i in range(N):
    coins.append(int(input()))

while K != 0:
    tmp = coins.pop()
    
    if K >= tmp:
        result += int(K/tmp)
        K = K%tmp
    else:
        continue

print(result)
    0415 Review
    groovy解析hello world