[백준] 1106번: 호텔 [C#]

 

N개의 도시에 홍보를 하여 K의 금액을 들여 I명의 고객을 증가시킬 때,

적어도 C명의 고객을 늘리는데 필요한 최소한의 금액을 적으면 된다.

지금까지는 '최대한' 이 조건이었지만, 이번에는 '최소의' 금액이므로 주의를 해야한다.

 

 

using System.IO;
using System.Text;
using System.Linq;
using System.Reflection.PortableExecutable;
using System.Security.Cryptography;
using System.Runtime.Intrinsics.Arm;
 
namespace 연습장
{
    internal class Program
    {
        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[] input = Console.ReadLine().Split().Select(int.Parse).ToArray();
            int people = input[0];
            int cities = input[1];
 
            int[] dp = Enumerable.Repeat(int.MaxValue, people+100).ToArray();
 
            dp[0] = 0;
            for (int i = 0; i < cities; i++)
            {
                input = Console.ReadLine().Split().Select(int.Parse).ToArray();
                int coast = input[0];
                int increase = input[1];
                for (int j = increase; j < dp.Length; j++)
                {
                    if (dp[j - increase] != int.MaxValue)
                        dp[j] = Math.Min(dp[j], coast + dp[j - increase]);
                }
            }
 
            int res = int.MaxValue;
            for (int i = people; i < dp.Length; i++)
            {
                res = Math.Min(res, dp[i]);
            }
            Console.WriteLine(res);
        }
    }
}
 

 

최소의 금액을 구하기 위해 dp의 0을 제외한 모든 원소를 int형의 최대값으로 설정해 주었다.

이후 K의 배수마다 K의 배수를 넣어주고, 모든 입력에 대해서 반복한다.

이후 C부터 dp의 끝까지 반복하며 가장 작은 사용 금액을 출력해준다.