백준#11047-동전 0

https://www.acmicpc.net/problem/11047

11047번: 동전 0

그리디 알고리즘으로 분류된 동전 0 문제 입니다.

 

우선 주어지는 동전의 값어치 중 1원짜리는 항상 A[0]에 있으므로 문제가 풀리지 않는 경우는 없습니다.

 

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
 
namespace _11047
{
    class Program
    {
        static void Main(string[] args)
        {
            string[] inputArray = Console.ReadLine().Split(' ');
            int coinTypeCount = int.Parse(inputArray[0]);
            int money = int.Parse(inputArray[1]);
            int needCoin = 0;
 
            List<int> coinList = new List<int>();
 
            for (int i = 0; i < coinTypeCount; i++)
                coinList.Add(int.Parse(Console.ReadLine().Trim()));
 
            //핵심 부분.
            for(int i = coinList.Count - 1; i >= 0; i--)
            {
                needCoin += money / coinList[i];
                money = money % coinList[i];
            }
 
            //여기까지.
 
            Console.WriteLine(needCoin);
        }
    }
}

핵심 부분이 이 문제의 전체 입니다. 나머지는 변수 입력 및 초기화 입니다.

동전의 값이 소트가 되어 있으므로 가장 금액이 큰 동전부터 주어진 돈에 나누어

몫을 동전의 갯수로 더하고 나머지를 다음 동전으로 진행 했습니다.

 

동전의 값이 주어진 돈보다 커져서 나눠지지 않아도 상관 없습니다. 몫이 0이므로

동전의 갯수는 늘어나지 않으며 돈을 동전으로 나눈 나머지 또한 처음 돈의 값 그대로 들어갑니다.

 

좀더 빨리 종료하려면 money가 0이될 때 종료하면 되겠습니다.