[백준] 2293번: 동전 1 [C#]

 

 

금액 k가 주어지고 n종류의 동전이 주어진다.

주어진 동전을 이용해서 k원을 몇 번 만들 수 있는지 출력하면 된다.

 

using System.IO;
using System.Text;
using System.Linq;
using System.Reflection.PortableExecutable;
using System.Security.Cryptography;
 
namespace 연습장
{
    internal class Program
    {
        //static List<int> stack = new List<int>();
        static int possibility = 0;
        static int pre_i = 0;
        static StringBuilder sb = new StringBuilder();
        static void Main(string[] args)
        {
            using var reader = new StreamReader(Console.OpenStandardInput());
            using var print = new StreamWriter(Console.OpenStandardOutput());
 
            int[] arr = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
 
            int money = arr[1];
 
            int[] coin = new int[arr[0]];
 
            for (int i = 0; i < arr[0]; i++)
            {
                coin[i] = int.Parse(Console.ReadLine());
            }
 
            is_possible(money, coin, pre_i);
            Console.WriteLine(possibility);
 
        }
        static void is_possible(int money, int[] coin, int pre_i)
        {
 
            for (int i =0; i < coin.Length; i++)
            {
                if (i < pre_i)
                    continue;
                if (money - coin[i] == 0)
                {
                    possibility++;
                    return;
                }
                if (money % coin[i] >= 0)
                {
                    pre_i = i;
                    is_possible(money - coin[i], coin, i);
                }
            }
        }
    }
}

 

처음에는 어떻게 풀어야 할지 도무지 생각이 안 나서 일단 때려 맞히기 형식으로 재귀함수를 이용한 부르트 포스 형식으로 풀었다. 실행 시간이 0.5초 미만이어야 하는 조건이기 때문에, 일단 구현이라도 해보자는 마음으로 작성했다.

물론 결과는 당연히 시간초과.

using System.IO;
using System.Text;
using System.Linq;
using System.Reflection.PortableExecutable;
using System.Security.Cryptography;
 
namespace 연습장
{
    internal class Program
    {
        //static List<int> stack = new List<int>();
        static int possibility = 0;
        static int pre_i = 0;
        static StringBuilder sb = new StringBuilder();
        static void Main(string[] args)
        {
            using var reader = new StreamReader(Console.OpenStandardInput());
            using var print = new StreamWriter(Console.OpenStandardOutput());
 
            int[] arr = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
            int n = arr[0];
            int k = arr[1];
 
            int[] coin = new int[n];
 
            for (int i = 0; i < n; i++)
                coin[i] = int.Parse(Console.ReadLine());
 
            int[] dp = new int[k + 1];
 
            dp[0] = 1;
 
            for (int i = 0; i < coin.Length; i++)
            {
                for (int j = coin[i]; j <= k; j++)
                {
                    dp[j] += dp[j - coin[i]];
                }
            }
            Console.WriteLine(dp[k]);
 
        }
    }
}

 

동적 프로그래밍이라는 게 있다고 하더라.

개념은 단순한데, 복잡한 문제를 쉬운 문제들로 나눠서 푸는 방식?이라고 한다?

아무튼 내가 이해한 바로는 배열을 이용해, 전 단계의 결과를 저장하고, 전 단계의 결과로부터 영향을 받아서 계산 횟수를 최소화하는 방식인 거 같다.

풀기는 했지만, 서핑에 의존한 영향이 커서, 내일이나 내일 모래에 다시 풀어봐야겠다.