백준 29704번: 벼락치기

문제: https://www.acmicpc.net/problem/29704

문제 풀이

DP

dp[i] = i일을 소요해 풀 수 있는 문제들의 벌금의 합 중 최댓값

total = 모든 문제의 벌금의 합

max = T일 내에 풀 수 있는 문제들의 벌금의 합 중 최댓값

문제마다 걸리는 시간, 벌금이 있고 벌금을 최대한 적게 내도록 문제를 풀어야 하므로 문제의 벌금이 최대로 되도록 고르는 배낭 문제가 됨

따라서 dp[i]를 i일 내에 풀 수 있는 문제들의 벌금의 합으로 정의하고 다음 점화식에 맞게 값을 구함

$dp[i] = max(dp[i], dp[i - d] + m)$

max에 dp 배열에 저장된 값중 최댓값을 저장하면 T일 내에 풀 수 있는 벌금의 합 중 최댓값이 되므로 전체 벌금 total에서 이 값을 빼서 출력하면 정답

풀이 설명

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

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

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

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

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

문제를 해결하는 데 소요되는 일과 벌금이 주어질 때 T일 내에 내는 벌금이 최소가 되도록 하는 문제이다. 이를 다시 생각하면 문제당 시간과 가중치가 주어질 때 최대한 가중치가 높게 되도록 문제를 고르는 문제이다.

문제 당 해결하는 데 걸리는 시간이 주어져 있으므로 문제를 하나 푼다면 남은 날짜가 그만큼 줄어드는 것이므로 그 남은 날짜와 나머지 문제들에 대해 다시 최대한 가중치가 높도록 문제를 고르는 문제가 된다.

즉, 다시 작은 문제로 나눌 수 있다는 점에서 이 문제를 DP로 풀 수 있다는 점이 된다. 그러므로 i일 내로 풀 수 있는 문제의 최대 가중치를 dp[i]로 정의한다. 현재 문제를 해결하는 데 소요되는 일을 d, 현재 문제의 벌금(가중치)를 m라고 하면 현재 문제를 풀었을 때의 최대 가중치는 dp[i - d] + m, 현재 문제를 풀지 않았을 때의 최대 가중치는 dp[i]가 되므로 다음과 같은 점화식이 나온다

$dp[i] = max(dp[i], dp[i - d] + m)$

이 점화식에 따라 배열에 값을 채우면 되는데 인덱스를 오름차순 순서로 반복하게 된다면 같은 문제를 반복해서 푸는 문제가 생기기 때문에 내림차순 순서로 반복해야 정상적으로 문제가 한 번만 들어가게 된다.

모든 문제에 대해 dp 배열을 구하면 푼 문제의 벌금의 합 중 최댓값을 구해야 하므로 max에 dp 배열에 저장된 값의 최댓값을 저장하고 이 값이 T일 내에 풀 수 있는 문제들의 벌금의 합 중 최댓값이므로 전체 벌금에서 이 값을 빼면 내야하는 벌금의 최솟값이 되므로 출력하면 정답이 된다.

소스 코드

import java.io.StreamTokenizer

fun main() = StreamTokenizer(System.`in`.bufferedReader()).run {
    fun nextInt(): Int{
        nextToken()
        return nval.toInt()
    }
    val N = nextInt()
    val T = nextInt()
    val dp = IntArray(T + 1)
    var total = 0
    repeat(N){
        val d = nextInt()
        val m = nextInt()
        total += m
        for(i in T downTo d){
            dp[i] = maxOf(dp[i], dp[i - d] + m)
        }
    }
    var max = 0
    for(i in 1..T){
        max = maxOf(max, dp[i])
    }
    println(total - max)
}