[백준] 2293 동전 1 [DP]

 

이번 단계가 저번 단계의 결과값을 포함하고 있음을 이용한 문제이다

수업듣고 써야지

 

using System;
using System.Collections.Generic;
using System.Text;
using System.Linq;
using System.Threading.Channels;
 
namespace real연습
{
    internal class Program
    {
        static void Main(string[] args)
        {
            int[] arr = Array.ConvertAll(Console.ReadLine().Trim().Split(), int.Parse);
            int[] dp = new int[arr[1] + 1];
            dp[0] = 1;
 
            for (int i = 0; i < arr[0]; i++)
            {
                int coin = int.Parse(Console.ReadLine());
                for (int j = coin; j <= arr[1]; j++)
                {
                    dp[j] += dp[j - coin];
                }
            }
            Console.WriteLine(dp[arr[1]]);
        }
    }
}