[BOJ] 5585번 거스름돈

복기

해당 문제가 그리디로 풀었을 때 정당성을 가지는 이유는 가지고 있는 거스름돈의 큰 단위가 항상 작은 단위의 배수기 때문이다.

코드

• C++ 17

#include <stdio.h>   int M; int Rests[] = { 500, 100, 50, 10, 5, 1 };   int main() {     scanf("%d", &M);     int target = 1000 - M;       int ans = 0;     for (int i = 0; i < 6; ++i)     {         ans += target / Rests[i];         target %= Rests[i];     }       printf("%d\n", ans); }

• C# 6.0

using System;   namespace Csharp {     class Program     {         static readonly int TARO_MONEY = 1000;           static int M;         static int[] Rests = new int[] { 500, 100, 50, 10, 5, 1 };           static void Main(string[] args)         {             M = Convert.ToInt32(Console.ReadLine());             int target = TARO_MONEY - M;                          int ans = 0;             for (int i = 0; i < Rests.Length; i++)             {                 ans += target / Rests[i];                 target %= Rests[i];             }               Console.WriteLine(ans);         }     } }

• Python 3

M = int(input()) target = 1000 - M   ans = 0 rests = [ 500, 100, 50, 10, 5, 1 ] for rest in rests:   ans += target // rest   target %= rest   print(ans)