硬貨の枚数を減らす
500 ウォン、100 ウォン、50 ウォン、10 ウォン硬貨がいくらでもある。
ちょうど n ウォンを払うのに使う硬貨の枚数の最小値を出力せよ。
- 入力
- 10 ≤ n ≤ 1,000,000,000 で、n は 10 の倍数である。
- 出力
- 硬貨の枚数の最小値
1880
10
40
4
エラー一覧00F8 ↓ · ⇧F8 ↑
入力(stdin)
実行すると、これらの行が順に input()・標準入力に渡されます(実行中に入力を求めません)。
$ 準備完了
コードを入力して解くにはパソコンで開いてください。モバイルでは問題と解答を見られます。
ほかの言語では？言語別の解答を見る · 8 言語の解答
大きい硬貨から商の分だけ使い、余りに進む貪欲法です。
この硬貨は大きいほうがいつもすぐ下の倍数（500 = 5×100、100 = 2×50、50 = 5×10）なので、貪欲法で最小が保証されます — 10・40・50 ウォンなら 80 ウォンで 50+10+10+10（4 枚）より 40+40（2 枚）が少なく、うまくいきません。
言語の違いは割り算です：C・C++・Java・C# の int / int と Python の // は商を返しますが、JavaScript・TypeScript の / は 1880 / 500 = 3.76 のように小数まで割るので Math.floor が必要です。
Craykon も / は小数までなので 数学.商(n, coin) を使い、余りはどこでも % です。
小さい硬貨から使うと全部 10 ウォンになるので、順番も大事です。
n = int(input())count = 0for coin in [500, 100, 50, 10]: count += n // coin n %= coinprint(count)let n = Number(require("fs").readFileSync(0, "utf8").trim());let count = 0;for (const coin of [500, 100, 50, 10]) { count += Math.floor(n / coin); n %= coin;}console.log(count);import { readFileSync } from "node:fs";let n: number = Number(readFileSync(0, "utf8").trim());let count = 0;for (const coin of [500, 100, 50, 10]) { count += Math.floor(n / coin); n %= coin;}console.log(count);import java.util.Scanner; public class Main { public static void main(String[] args) { int n = new Scanner(System.in).nextInt(); int count = 0; for (int coin : new int[] {500, 100, 50, 10}) { count += n / coin; n %= coin; } System.out.println(count); }}using System; class Program{ static void Main() { int n = int.Parse(Console.ReadLine().Trim()); int count = 0; foreach (int coin in new[] { 500, 100, 50, 10 }) { count += n / coin; n %= coin; } Console.WriteLine(count); }}#include <iostream> int main() { int n, count = 0; std::cin >> n; for (int coin : {500, 100, 50, 10}) { count += n / coin; n %= coin; } std::cout << count << '\n';}#include <stdio.h> int main(void) { int n, count = 0; const int coins[] = {500, 100, 50, 10}; scanf("%d", &n); for (int i = 0; i < 4; i++) { count += n / coins[i]; n %= coins[i]; } printf("%d\n", count); return 0;}n = コンソール.行読み().数に();count = 0;それぞれ (coin の中 [500, 100, 50, 10]){ count += 数学.商(n, coin); n = n % coin;}コンソール.書く(count);