백준 2073 수도배관공 (C++)

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

#include <iostream>
#include <vector>
#include <algorithm>

#define MAX 987654321

using namespace std;



int main() {

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int d, p;
    cin >> d >> p;

    vector<pair<int, int>> pipe(p);
    vector<int> dp(d + 1, 0);           //dp[i]: 수도관 길이를 i까지 이었을 때의 최대 용량

    for (auto &item: pipe) {
        cin >> item.first >> item.second;           //길이, 용량
    }

    dp[0] = MAX;
    for (int i = 0; i < p; i++) {
        for (int j = d; j >= pipe[i].first; j--) {
            dp[j] = max(dp[j], min(dp[j - pipe[i].first], pipe[i].second));
        }
    }

    cout << dp[d];

    return 0;
}

1. 문제

아기염소들이 언덕에서 풀을 뜯고 놀다 보면 항상 도중에 목이 마르곤 했다. 그들은 불편함을 참지 못하고 수도관을 설치하여 거리 D(7 ≤ D ≤ 100,000)만큼 떨어진 곳의 강에서 물을 끌어오기로 했다. 근처의 인간 마을에서 P개(1 ≤ P ≤ 350)의 파이프를 매입했는데, 각각은 길이 Li와 용량 Ci로 나타낼 수 있다. (Li와 Ci는 모두 223보다 작거나 같은 양의 정수이다)

파이프들은 일렬로 이어서 수도관 하나로 만들 수 있으며, 이때 수도관의 용량은 그것을 이루는 파이프들의 용량 중 최솟값이 되고, 수도관의 길이는 파이프들 길이의 총합이다.

수도관을 한 개 만들어 총 길이가 정확히 D와 같게 할 때, 가능한 최대 수도관 용량을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 D와 P가 주어진다. 두 번째 줄부터 P개의 줄이 차례로 주어지고, 각 줄마다 Li와 Ci가 주어진다. 길이 합이 D가 되게 하는 수도관의 부분집합이 적어도 하나 존재한다.

출력

가능한 최대 수도관 용량을 첫째 줄에 출력한다.

2. 풀이

    dp[0] = MAX;
    for (int i = 0; i < p; i++) {
        for (int j = d; j >= pipe[i].first; j--) {
            dp[j] = max(dp[j], min(dp[j - pipe[i].first], pipe[i].second));
        }
    }

•  dp[i]: 수도관 길이를 i까지 이었을 때의 최대 용량

 길이 j의 파이프를 만드는 경우는 다음의 2가지로 나눌 수 있다.

• i번 파이프를 사용하지 않는 경우: 현재까지의 조립된 j 길이의 파이프 중 최대 용량 dp[j]
• i번 파이프를 사용하는 경우: i번 파이프의 용량과 j-(i번 파이프의 길이) 길이를 만들 때 필요한 용량 중 작은 값

ex) 길이 7의 파이프를 만드는 데 i번 파이프가 (3, 7)이라고 하자. 문제에 의해 수도관의 용량은 구성 파이프의 용량 중 최솟값이므로 만약 (4, 3)의 파이프가 있다면 두 파이프를 이었을 때의 용량은 더 작은 값인 3이다. 이 파이프를 dp[7]과 비교하는 데 2, 5의 파이프를 이은 용량이 4라면 이 방식을 택해야 한다.

 

두 경우 중 최댓값을 구해나가면 최대 수도관 용량을 구할 수 있다.