[백준] 22115번: 창영이와 커피 [C#]

이 예제보다는 아래의 테스트 케이스를 시도해보는걸 추천드립니다.

100 100000
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100

 

창영이가 N종류의 커피를 '단 한개' 씩 가지고있을 때, 창영이가 K만큼의 커피를 마시기 위한 커피의 최소 개수를 구하는 문제이다.

커피를 한잔씩만 마실 수 있기 때문에, 지금까지와는 다른 접근 방식으로 문제를 풀어야 한다.

 

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 n = input[0]; // 커피 종류
            int k = input[1]; // 섭취할 카페인
 
            int[] dp = Enumerable.Repeat(int.MaxValue, k + 1).ToArray(); // dp의 모든 원소를 int형의 최대값으로 초기화
            dp[0] = 0; // 0은 0으로 초기화
 
            int[] coffee = Console.ReadLine().Split().Select(int.Parse).ToArray(); // 각 커피의 카페인
 
            for (int i = 0; i < n; i++) // 커피의 종류를 순차 참조
            {
                for (int j = k; j >=  coffee[i]; j-- ) // 목표하는 카페인 부터 역순 참조
              // 이렇게 하면 커피를 중복으로 마시는걸 방지할 수 있다. {
                    if (dp[j - coffee[i]] != int.MaxValue)
                        dp[j] = Math.Min(dp[j], 1 + dp[j - coffee[i]]);
                }
            }
 
            Console.WriteLine((dp[k] == int.MaxValue) ? "-1" : dp[k]);
 
        }
    }
}
 

 

문제 자체는 필요한 값까지 최소 몇번의 섭취가 있어야 하는지 구하면 되는 어려울 거 없는 문제이다.

하지만, 이 문제의 핵심은 바로 단 한번씩만 커피를 마실 수 있다는 것.

이 조건을 만족하기 위해서 두번째 for문을 for (int j = 0; j < k; j++) 에서  for (int j = k; j >=  coffee[i]; j-- ) 로 바꿔 주어야 한다.