동전 개수 줄이기
500원, 100원, 50원, 10원짜리 동전이 얼마든지 있다.
n원을 거슬러 줄 때 쓰는 동전 개수의 최솟값을 출력하라.
- 입력
- 10 ≤ n ≤ 1,000,000,000이고, n은 10의 배수이다.
- 출력
- 동전 개수의 최솟값
1880
10
40
4
오류 목록00F8 ↓ · ⇧F8 ↑
입력(stdin)
실행하면 이 줄들이 차례로 input()·표준 입력으로 들어가요(실행 중에 묻지 않아요).
$ 준비됐어요
코드를 입력해 풀려면 PC에서 열어 주세요. 모바일에서는 문제와 풀이를 볼 수 있어요.
다른 언어로는?언어별 풀이 보기 · 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가 필요해요.
크레이콘도 /는 소수까지라 수학.몫(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);