백준 5585번 거스름돈 C#풀이

1000원을 내고 최소 몇개의 동전으로 거스름돈을 받을수있는지 출력하는 문제입니다.

그리디 알고리즘을 사용해요

using System;
class Program
{
    static void Main(string[] args)
    {
        // 받을 거스름돈입니다.
        int change = 1000 - int.Parse(Console.ReadLine());
 
        // 나중에 출력할 받을 동전의 최소 개수입니다.
        int count = 0;
 
        // 내림차순으로 정렬되있는 동전의 종류입니다. 
        int[] coins = { 500, 100, 50, 10, 5, 1 };
 
        // 동전의 개수만큼 for문을 실행합니다.
        // 동전의 순서는 내림차순이기때문에 500원부터 시도합니다.
        for (int i = 0; i < coins.Length; i++)
        {
            // 만약 i번째 동전으로 나눠지지 않는다면
            // 바로 넘어가고 더 값이 작은 동전으로 시도합니다.
            if (change / coins[i] < 1) continue;
 
            // count에 몫을 더합니다.
            count += change / coins[i];
 
            // change를 coins[i]로 나누고 나머지를 change에 넣습니다.
            change %= coins[i];
 
            // 받을 잔돈이 0이면 반복을 종료합니다.
            if (change == 0) break;
        }
        Console.WriteLine(count);
    }
}

수고하셨습니다.