[백준] 14728번: 벼락치기 [C#

 

가방문제와 동일한 문제이다.

남은 시간동안 최대 몇점의 점수를 확보할 수 있는지 구하는 문제이다.

 

using System.IO;
using System.Text;
using System.Linq;
using System.Reflection.PortableExecutable;
using System.Security.Cryptography;
 
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 = Array.ConvertAll(reader.ReadLine().Split(), int.Parse);
            int objects = input[0];
            int leftTime = input[1];
 
            int[] Time = new int[objects];
            int[] Score = new int[objects];
 
            int[,] dp = new int[objects + 1, leftTime + 1];
 
            for (int i = 0; i < objects; i++)
            {
                input = Array.ConvertAll(reader.ReadLine().Split(), int.Parse);
                Time[i] = input[0];
                Score[i] = input[1];
            }
 
            for (int O = 0; O <= objects; O++)
            {
                for (int T = 0; T <= leftTime; T++)
                {
                    if (O == 0 || T == 0)
                        dp[O, T] = 0;
                    else if (Time[O - 1] <= T)
                        dp[O, T] = Math.Max(dp[O - 1, T], Score[O - 1] + dp[O - 1, T - Time[O - 1]]);
                    else
                        dp[O, T] = dp[O - 1, T];
                }
            }
 
            print.WriteLine(dp[objects, leftTime]);
 
        }
    }
}

 

dp에 따르면 모든 배열의 칸에는 해당 케이스의 최적의 값이 들어있으므로, 조건에 따라 경우의 수를 계산 한 다음 마지막 칸을 출력하면 된다.

그리고, dp 배열은 0인 케이스를 제외하고 생각하기 때문에, 한칸씩 늘어난 형태이지만, score와 time 배열은 그렇지 않기 때문에, for문을 돌릴 때 <= 을 사용해야한다는 걸 (혹은 조건+ 1) 기억해두자.