[백준] 2294번: 동전 2 [C#]

이전의 동전 문제가 k원을 만드는 경우의 수를 세는 문제였다면, 이번에는 k원을 가장 적은 동적을 사용해서 만들었을 때 사용한 동전 개수를 구하는 문제이다.

 

 

using System.IO;
using System.Text;
using System.Linq;
using System.Reflection.PortableExecutable;
using System.Security.Cryptography;
 
namespace 연습장
{
    internal class Program
    {
        static StringBuilder sb = new StringBuilder();
        static void Main(string[] args)
        {
            int[] input = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
            int n = input[0];
            int k = input[1];
 
            int[] coin = new int[n];
            for (int i =0; i < n; i++)
                coin[i] = int.Parse(Console.ReadLine());
 
            int[] dp = Enumerable.Repeat(int.MaxValue, k + 1).ToArray();
            dp[0] = 0;
 
            for (int j = 0; j < n; j++)
            {
                for (int l = coin[j]; l < dp.Length; l++)
                {
                    if (dp[l - coin[j]] != int.MaxValue )
                    dp[l] = Math.Min(dp[l], 1 + dp[l - coin[j]]);
                }
            }
            
            Console.WriteLine(dp[k] == k ? dp[k] : -1);
        }
    }
}
 

최소값을 구해야 하므로, dp배열의 모든 원소를 int형의 최대값으로 바꾸어 준 뒤, 0번지만 0으로 설정해 두었다.

이후, 계산을 통해 각 n원을 만드는데 드는 가장 적은 동전의 개수를 구하여, 출력해 주었다.