科学の箱

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

pandaの基本中の基本操作

numpyとpandaのインポート import numpy as np import pandas as pd 前準備 labels = [‘a’, ‘b’, ‘c’] mydata = [10,2 …

no image

flickrapiを使うための手順

https://stuvel.eu/flickrapiで提供されるflickrapiを利用するにあたり、エラーが出てインストールできない。 condaでは提供されていない pipはSSLError(S …

no image

janomeで品詞を解析する

  import sys import os from glob import glob from janome.tokenizer import Tokenizer def main(): …

no image

graphvizのコマンドラインから実行

dot -Kdot -Tpng test.dot -o test.png Related posts:numpyで配列を抜き出す方法scikit-learnで適切なアルゴリズムを選択するためのチートシ …

no image

配列をリストから生成

配列をリストから生成 numpyにおける配列はnp.arrayを使って生成する。最も基本となる方法はnp.arrayに引数としてリストを渡してやる方法である。 まずは整数の配列を生成してみる。 pri …

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

side bar top



アーカイブ

カテゴリー