C# 11047번 동전 0

문제

코드 :

using System;

namespace _1
{
    class Program
    {
        static void Main(string[] args)
        {
            //초기화
            int[] inputData = Array.ConvertAll(Console.ReadLine().Split(' '), int.Parse);
            int N, K, count;           
            N = inputData[0];
            K = inputData[1];
            count = 0;
            
            //Won담을 행렬
            int[] Won = new int[N];


            for (int i = 0; i < N; i++)
            {
                Won[i] = int.Parse(Console.ReadLine());
            }

            //가장 큰 돈으로 먼저 나눠서 나눌 수 있는지를 확인해야함
            //예를들어 52000원이면 50000원부터 나눌 수 있음
            for (int i = N-1; i >= 0; i--)
            {   
                //나눌수 있다면
                if (K/Won[i] != 0)
                {
                    //몫이 해당 Won으로 나눌 수 있는 값이기 때문에 count에 추가
                    count += K / Won[i];
                    //K는 나눈 값은 빼고 나머지만 있으면 위와 같은 작업을 반복할 수 있음
                    K = K % Won[i];
                }
            }

            Console.WriteLine( count);
        }
    }
}

문제 풀이 :

동전 문제가 나오면 DP로 풀어야 하는지 그리디로 풀어야하는지를 구별할 수 있어야 한다.

그리디로 풀리는 문제의 경우 대체로 동전의 종류가 서로 배수이다. 

그러나 만약 동전의 종류가 1,3,4,5 처럼 서로가 배수가 아닐 경우 7원을 가장 적은 동전으로 표현하기 위해서

그리디로 풀게 될 경우 5원 1개, 1원 2개가 된다. 하지만 4원 1개, 3원 1개가 더 적음을 알 수 있다.