[ BOJ ] 29704 : 벼락치기 ( GOLD 5 ) / Python

문제

숙명여자대학교의 알고리즘 학회 ALGOS에 합격한 혜민이는 너무 기뻐 마음이 들뜬 나머지 프로그래밍 과제가 있는 것을 잊어버리고 말았다. 프로그래밍 과제로는 다양한 난이도의 문제 N개가 주어지고, 앞으로 T일의 제출 기한이 남아있다. 만약 제출 기한 내에 문제를 제출 못 하면, 제출하지 못한 문제마다 정해져 있는 벌금을 내야 한다. 혜민이는 벌금을 내고 싶지 않기 때문에, 내는 벌금의 총금액이 가능한 한 적어지도록 문제를 풀려고 한다.

문제를 해결하는 데 소요되는 일수와 그 문제를 제출 기한 내에 해결하지 못할 경우 내야 하는 벌금이 주어질 때, 혜민이가 내야 하는 벌금의 최소 금액을 구해보자. 제출 기한 T일이 지났을 때, 제출하지 못한 문제별 벌금의 합이 혜민이가 최종적으로 내야 하는 벌금이다. 단, 혜민이는 아직 프로그래밍에 익숙하지 않아서 한 번에 한 개의 문제만 해결할 수 있다.

	해결하는 데 소요되는 일수	벌금
문제1	2	5000
문제2	1	1000
문제3	1	2000

예를 들어, 프로그래밍 과제로 위와 같이 3개의 문제가 주어졌다고 가정해 보자. 제출 기한이 3일 남았다면, 첫째 날에 3번 문제를 해결하고, 둘째 날과 셋째 날에 걸쳐 1번 문제를 해결하면 2번 문제의 벌금인 1,000원만 내면 된다.

혜민이가 가능한 한 적은 벌금을 낼 수 있게 도와주자.

입력

첫째 줄에 문제의 개수 N (1 ≤ N ≤ 1000)과 남은 제출 기한 T (1 ≤ T ≤ 1000) 가 주어진다.

둘째 줄부터 N개의 줄에 걸쳐 i번 문제를 푸는 데 걸리는 일수 d_i (1 ≤ d_i ≤ 1000)와 해당 문제의 벌금 m_i (1 ≤ m_i ≤ 5000) 이 주어진다.

출력

최종적으로 내는 벌금이 최소가 되도록 문제를 풀었을 때, 혜민이가 내야 하는 벌금을 출력한다.

만약, 기한 내에 모든 문제를 해결할 수 있다면 0을 출력한다.

풀이 과정

기본 배낭 DP로 풀이했다. 주어진 일 수 안에 최대한 많은 벌금을 DP 에 모을 수 있도록 하여 DP[i][j] : i번째 문제를 풀거나 풀지 않았을 때 뺄 수 있는 최대 벌금 식을 세웠다. 총 벌금 합에서 DP[n][t] 값을 빼면 된다.

import sys 
input = sys.stdin.readline

n, t = map(int, input().rstrip().split())
arr = [list(map(int, input().rstrip().split())) for _ in range(n)]
sum_value = sum([arr[i][1] for i in range(n)])

dp = [[0 for _ in range(t+1)] for _ in range(n+1)]

for weight_limit in range(1, t+1):
    for thing in range(1, n+1):
        now_weight = arr[thing-1][0]
        now_value = arr[thing-1][1]

        if weight_limit >= now_weight:
            dp[thing][weight_limit] = max(dp[thing-1][weight_limit], dp[thing-1][weight_limit - now_weight] + now_value)
        else:
            dp[thing][weight_limit] = dp[thing-1][weight_limit]

print(sum_value - dp[n][t])