📖 백준 2073번 : https://www.acmicpc.net/problem/2073
조건
| 시간 제한 | 메모리 제한 |
|---|---|
| 2 초 | 128 MB |
문제
아기염소들이 언덕에서 풀을 뜯고 놀다 보면 항상 도중에 목이 마르곤 했다. 그들은 불편함을 참지 못하고 수도관을 설치하여 거리 D(7 ≤ D ≤ 100,000)만큼 떨어진 곳의 강에서 물을 끌어오기로 했다. 근처의 인간 마을에서 P개(1 ≤ P ≤ 350)의 파이프를 매입했는데, 각각은 길이 Li와 용량 Ci로 나타낼 수 있다. (Li와 Ci는 모두 223보다 작거나 같은 양의 정수이다)
파이프들은 일렬로 이어서 수도관 하나로 만들 수 있으며, 이때 수도관의 용량은 그것을 이루는 파이프들의 용량 중 최솟값이 되고, 수도관의 길이는 파이프들 길이의 총합이다.
수도관을 한 개 만들어 총 길이가 정확히 D와 같게 할 때, 가능한 최대 수도관 용량을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 D와 P가 주어진다. 두 번째 줄부터 P개의 줄이 차례로 주어지고, 각 줄마다 Li와 Ci가 주어진다. 길이 합이 D가 되게 하는 수도관의 부분집합이 적어도 하나 존재한다.
출력
가능한 최대 수도관 용량을 첫째 줄에 출력한다.
풀이
일반적인 배낭문제와 같다. 하지만 2차원 dp를 구성해서 풀어내려고 하면 메모리 제한에 걸리므로, 1차원 dp로 풀어야한다. 나는 dp[i]를 정확히 i만큼의 길이를 가지는 수도관을 구성했을 때의 최대 용량을 갖는다고 생각했다.
새로 파이프를 추가했을 때, 수도관의 전체 용량은 min(dp[x-Li],Ci)이다.
이 값이 기존에 길이 x를 만들 때의 수도관 용량보다 크면 갱신한다. 각 파이프는 한 번씩만 사용할 수 있으므로, 0-1 knapsack처럼 길이 x에 대해 x = D부터 Li까지 역순으로 업데이트하면 올바르게 갱신되는 것을 알 수 있다. 순방향으로 업데이트하면 이미 이전에 사용한 파이프에 대해서 중복으로 값이 계산되므로 처리가 복잡해진다.
dp[x] = max(dp[x],min(dp[x-Li],Ci))
아직 아무런 파이프도 사용하지 않은 상태에서 길이 0인 경우는, 아무런 제약이 없으므로 용량을 무한대로 생각할 수 있다. dp[0]을 2^23 보다 큰 값으로 설정하고 0이 아닌 다른 값은 아직 만들지 못한 상태이므로 0으로 초기화했다.
코드
#include <iostream>
using namespace std;
int dp[100001], L[350], C[350];
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
int d, p;
cin >> d >> p;
for (int i = 0; i < p; i++) {
cin >> L[i] >> C[i];
}
dp[0] = 1 << 24;
for (int i = 0; i < p; i++) {
for (int j = d; j >= L[i]; j--) {
dp[j] = max(dp[j], min(dp[j - L[i]], C[i]));
}
}
cout << dp[d];
return 0;
}