[BOJ][C#] 2294 동전 2

📕 문제

📌 링크

📘 코드

namespace BOJ
{
    class No_2294
    {
        const int MY_MAX = 10_000_000;

        static void Main()
        {
            using StreamReader input = new StreamReader(new BufferedStream(Console.OpenStandardInput()));
            using StreamWriter output = new StreamWriter(new BufferedStream(Console.OpenStandardOutput()));

            int[] inputs = Array.ConvertAll(input.ReadLine().Split(),int.Parse);
            int n = inputs[0];
            int k = inputs[1];

            int[] coins = new int[n+1];

            for(int i=0 ;i<n ; i++)
                coins[i] = int.Parse(input.ReadLine());

            int[] dp = new int[k+1];

            for(int i = 1 ; i <= k ; i++)
                dp[i] = MY_MAX;

            for(int i=0 ;i<n ;i++)
            {
                for(int j=1 ;j<=k ;j++)
                {
                    if(j >= coins[i])
                        dp[j] = Math.Min(dp[j], dp[j - coins[i]] + 1);
                }
            }

            dp[k] = dp[k] == MY_MAX ? -1 : dp[k];

            output.Write(dp[k]);
        }
    }
}

📙 오답노트

처음에 int.MaxValue로 배열을 초기화하였는데 + 1 하는 부분이 있어
int 범위를 초과하게 되어 틀렸었던 것 같다.
배열을 가상의 높은 수를 선언하여 초기화를 진행하고 제출하니 정답이였다.

📒 알고리즘 분류

• 다이나믹 프로그래밍