科学の箱

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

automated the boring – day 2

今日は簡単なUser認証のプロトタイプといえば恰好はよいが、 パスワードの入力 パスワードの突き合せ パスワードつきあわせの結果によりメッセージを変える name = ‘Mary’ password …

no image

condaでjupyter notebookが使えないとき

condaで環境を作るとjupyter notebookはインストールされていない。 この場合には個別にjupyterをインストールすればよい。   conda install jupyte …

no image

AtCoder ABC 174D Alter Altar

問題 左から右へN個の石が並んでいる。石の種類は白もしくは赤のいづれかである。 石について、下記の操作を何回でも実行できる。 2個の石を選んで場所を入れ替える(隣合ってなくてよい)。 1個の石を選んで …

no image

連続データのビジュアル

Kaggle TitanicのFareを使っていくつかビジュアル 金額別ヒストグラム-1 titanic_df[‘Fare’].plot(kind=’hist’, figsize=(15,3),bin …

no image

数字、計算、文字列を画面出力

Hello Worldができたので、いろいろな出力を試してみる。 出力はprint関数を使えばよい。 まずは数値から試してみる。数値は文字列と違い引用符で囲む必要はない。画面に直接表示するので変数は使 …

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

side bar top



アーカイブ

カテゴリー