ガジェット通信 GetNews

見たことのないものを見に行こう

第130回「今週のアルゴリズム:現地で使いやすい両替」正解者発表

DATE:
  • ガジェット通信 GetNewsを≫

「今週のアルゴリズム」とは

「今週のアルゴリズム」問題は、毎週火曜日にちょっとした問題を出題し、正解するとニックネームを掲載していくというシリーズ問題です。そして、正解した方全員に「たいへんよくできました」バッジも付与されます。

第130回は「今週のアルゴリズム:現地で使いやすい両替」の問題です。

問題文「第130回 今週のお題:現地で使いやすい両替」

第130回「今週のアルゴリズム:現地で使いやすい両替」正解者発表

日本から海外旅行に行く場合は外貨に両替しますが、海外からの旅行者が日本に来るときは日本円に両替します。
このとき、現時点でのレートに従って両替しますが、使うときに便利なように、紙幣や硬貨を組み合わせます。
できるだけ現地の文化を知りたいので、多くの種類を組み合わせて両替したいところです。

今回は米ドルから日本円への両替を考えます。
紙幣や硬貨の種類の数が最大になるもののうち、全体の枚数が最小になる両替方法を求め、その全体の枚数を出力してください。

例えば、1ドル112.54円のときに100ドルを日本円に交換すると11,254円で、その交換方法として以下のような例があります。
紙幣・硬貨
例1
例2
例3
例4
例5
1万円札
1
0
0
0
0
5千円札
0
1
1
1
1
2千円札
0
0
1
2
2
千円札
1
5
3
1
1
500円玉
0
2
2
1
2
100円玉
2
1
1
4
1
50円玉
1
2
1
4
2
10円玉
0
5
9
14
4
5円玉
0
0
2
2
2
1円玉
4
4
4
4
4
枚数
9
20
24
33
19

例1は紙幣や硬貨の種類が5種類、例2は7種類なのに対し、例3~5は9種類のため、例3~5の中から、全体の枚数が少ない例5を選びます。
(他のパターンの中でも、例5が最小になります。)

標準入力から両替後の日本円の金額が指定されたとき、紙幣・効果の種類が最大で全体の枚数が最小になる場合を求め、その時の枚数を標準出力に出力してください。
なお、入力されるのは整数のみで、最大でも50,000とします。

【入出力サンプル】
標準入力
11254

標準出力
19

正解者

おめでとうございます!正解者のみなさんです。(新着順)

strauss様
haruya様 

カテゴリー : デジタル・IT タグ :
CodeIQ MAGAZINEの記事一覧をみる ▶
  • 誤字を発見した方はこちらからご連絡ください。
  • ガジェット通信編集部への情報提供はこちらから
  • 記事内の筆者見解は明示のない限りガジェット通信を代表するものではありません。