[백준] 14728 - 벼락치기

1. 문제

14728번: 벼락치기

2. 개요

이번 시험의 단원 개수 N과 시험까지 공부 할 수 있는 총 시간 T가 주어진다.

둘째 줄부터 N 줄에 걸쳐서 각 단원 별 예상 공부 시간 K와 그 단원 문제의 배점 S가 주어진다.

해당 단원의 예상 공부 시간만큼, 혹은 그보다 더 많이 공부하면 무조건 문제를 맞출 수 있다고 할 때, 얻을 수 있는 최대 점수를 구하는 문제.

3. 풀이 및 코드

3-1. 풀이

[백준] 12865 - 평범한 배낭

와 같은 기본적인 배낭문제.

각 문제에 대해 이용 가능한 시각 (1부터 T까지)을 살펴보며 진행한다.

만약 해당 시각이 문제 풀이에 필요한 시간보다 크다면, 전 문제에 대한 해당 시각에 대한 최대 점수와 해당 시각 - 현 문제에 필요한 시각의 최대 점수를 비교해 값을 채워넣는다.

모든 문제, 시각에 대한 탐색을 끝냈다면 마지막 값을 출력한다.

3-2. Python

import sys

N, T = map(int, sys.stdin.readline().split())

dp = [[0 for _ in range(T + 1)] for _ in range(N + 1)]

chapters = []

for i in range(N):
    chapters.append(list(map(int, sys.stdin.readline().split())))

for i in range(1, N + 1):
    for j in range(1, T + 1):
        if j >= chapters[i-1][0]:
            dp[i][j] = max(dp[i-1][j], dp[i-1][j - chapters[i-1][0]] + chapters[i-1][1])

        else:
            dp[i][j] = dp[i-1][j]

print(dp[-1][-1])

3-3. C#

namespace boj_14728
{
    internal class Program
    {
        static void Main(string[] args)
        {
            string[] input = Console.ReadLine().Split();
            int N = int.Parse(input[0]);
            int T = int.Parse(input[1]);

            int[,] dp = new int[N + 1, T + 1];
            List<int[]> chapters = new List<int[]>();

            for (int i = 0; i < N; i++)
            {
                chapters.Add(Array.ConvertAll(Console.ReadLine().Split(), int.Parse));
            }

            for (int i = 1; i < N + 1; i++)
            {
                for (int j = 1; j < T + 1; j++)
                {
                    if (j >= chapters[i - 1][0])
                        dp[i, j] = Math.Max(dp[i - 1, j], dp[i - 1, j - chapters[i - 1][0]] + chapters[i - 1][1]);

                    else
                        dp[i, j] = dp[i - 1, j];
                }
            }

            Console.WriteLine(dp[N, T]);
        }
    }
}