科学の箱

科学・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

python data scientist bootcamp

pythonでdata分析をしたいと思ったが学校に通う時間もお金もない。udemyで検索したところ英語版であるが1400円!でコースが見つかったのでこちらを受けることにした。 https://www. …

no image

numpy.arange()を使って等差数列を生成する

等差数列を作るためにはnumpy.linspace()を使うと話をした。しかしlinspace()は要素数を指定するためにかえって混乱を招くことがある。そこで便利なのが公差を指定して配列を作ってくくれ …

no image

graphvizによる決定木の表示

graphvizの実行ファイルをインストール https://graphviz.gitlab.io/_pages/Download/Download_windows.html pythonにgraph …

no image

複数のグラフを表示する方法

ここでは以下を説明する。 複数のグラフを表示する2つの方法 サブプロットのグラフを整形 複数のグラフを表示する 複数のグラフを表示するためには二通りの方法がある。 subplots()を使ってあらかじ …

no image

kaggle Titanic Tutorial – 7

さて今回はAgeを補完してから、元の分布と比べてみる。 def fill_age(row): condition = ( (d_train_g_m[‘Sex’] == row[‘Sex’]) &amp …

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

side bar top



最近の投稿

アーカイブ

カテゴリー