科学の箱

科学・IT・登山の話題

AtCoder Python

蟻本 P42 硬貨の問題

投稿日:

貪欲法の基本

  1. その時点で最善の手を尽くす
  2. 尽くした結果を目的とする値に反映させる。
  3. 次善の手になるようにする。
  4. 1に戻る

硬貨の問題

A=int(input())
*C,=map(int,input().split())
coin=[1,5,10,50,100,500]

ans=0

for i in range(5,-1,-1):
    t=min(A//coin[i],C[i])
    A-=t*coin[i]
    ans+=t
print(ans)

 

気を付けるところ

  • 制限を考慮して、反映させる(minのところ)
  • 切り捨て a//coin[i]

メタ情報

inarticle



メタ情報

inarticle



-AtCoder, Python

執筆者:


comment

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です

関連記事

no image

kaggle Titanic Tutorial – 4

名前から取得できるタイトルを分析に利用してみる。 タイトルは末尾に”.”がついているのでこれを利用して切り出す。 def get_title(name): if ‘.’ in …

no image

kaggle Titanic Tutorial – 8

前回の結果がいまいちだった。これまではAgeは平均値でNullを埋めていた。平均値では明らか実際のデータと差異が出ると考えられる。そのためAgeがない情報についてより正確なAgeで補完するようにした。 …

no image

UnionFindのfindについて処理を考える。

UnionFindにおけるfind()もしくはroot()はルート(グループの根)を見つける処理である。 記述方法としては2種類ある。 whileループを回す 再帰処理 それぞれについて動きを確認して …

no image

Scrapy – Tutorial

Tutorialはこちら https://doc.scrapy.org/en/latest/intro/tutorial.html 特に難しい点はないがいくつかポイント spidersディレクトリはプ …

no image

タプルの操作

タプルはPythonで提供されているデータ構造の一つ。タプルは固定長で変更できない複数の値の集合である。 タプルオブジェクト (tuple object) — Python 3.8.0 ドキュメント …

2020年10月
« 9月   1月 »
 1234
567891011
12131415161718
19202122232425
262728293031  

side bar top



アーカイブ

カテゴリー