취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 29704번 문제인 벼락치기이다.
문제는 아래 링크를 확인하자.

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

잘 알려진 유형 중 하나인 knapsack dp 문제이다.

앞의 $i$가지 과제만을 고려하여 과제를 $t$일까지 했을 때 내지 않아도 되게 되는 벌금의 최댓값을 $dp[i][t]$와 같이 나타내자. $i+1$번째 과제를 해결하는 데에 드는 시간이 $d$, 벌금을 $w$라 할 때 $dp$는 대략적으로 아래와 같은 식을 만족한다:

$dp[i+1][t]=\text{max}(dp[i][t],dp[i][t-d]+w)$

여기서 $dp[i][t]$는 $i+1$번째 과제를 수행하지 않는 경우를, $dp[i][t-d]+w$는 $i+1$번째 과제를 수행하는 경우의 내지 않아도 될 벌금의 최댓값을 뜻한다.

대략적이라고 언급한 이유는 인덱스가 벗어나는 경우나 초기상태 등을 위에 제대로 언급해두지 않았기 때문이다. 이 부분은 특별할 것이 없으므로(아무 과제도 안 했을 때 dp의 값은 0일 것이다.) 설명을 생략하겠다. 단, 인덱스 등은 구현할 때 범위를 벗어나지 않게끔 신경 써 구현하자.

문제의 답은 내지 않아도 될 벌금의 최댓값이 아닌 내야 할 벌금의 최솟값임에 유의하자.

아래의 구현은 $i$의 값이 증가하면 두 단계 전의 $i$값에 대한 $dp$의 값을 다시 살펴볼 일이 없다는 점을 이용한 최적화가 포함되어 있다.

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;

int N, T, total;
int dp[1001];
int mx;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N >> T;
	while (N--) {
		int d, w; cin >> d >> w;
		total += w;
		for (int t = T; t >= d; t--) dp[t] = max(dp[t], dp[t - d] + w);
	}

	for (int i = 0; i <= T; i++) mx = max(mx, dp[i]);
	cout << total - mx;
}