[BOJ/백준] 02073 - 수도배관공사

---

DP[N] = 길이 N을 만들기위한 최대용량

---

---

• 제목

수도배관공사

---

• 조건

시간 제한 : 2 초

메모리 제한 : 128 MB 

---

• 문제

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

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

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

---

• 입력

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

---

• 출력

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

---

예제 입력1	예제 출력1
7 6 4 5 3 6 2 7 1 4 6 7 1 5	5

---

import java.io.*;
import java.util.*;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringBuilder sb = new StringBuilder();
    static StringTokenizer st;

    static class PIPE {
        int length;
        int capacity;

        PIPE(int length, int capacity) {
            this.length = length;
            this.capacity = capacity;
        }
    }

    public static void main(String[] args) throws IOException {
        st = new StringTokenizer(br.readLine());
        int D = Integer.parseInt(st.nextToken());
        int P = Integer.parseInt(st.nextToken());
        ArrayList<PIPE> pipe = new ArrayList<>();
        for (int i = 0; i < P; i++) {
            st = new StringTokenizer(br.readLine());
            int length = Integer.parseInt(st.nextToken());
            int capacity = Integer.parseInt(st.nextToken());
            pipe.add(new PIPE(length, capacity));
        }
        int[] dp = new int[D + 1];
        for (int i = 0; i < P; i++) {
            int length = pipe.get(i).length;
            int capacity = pipe.get(i).capacity;
            for (int j = D; j >= 0; j--) {
                if (j - length < 0) continue;
                dp[j] = Math.max(dp[j], Math.min(capacity, dp[j - length]));
            }
            dp[length] = Math.max(dp[length], capacity);
        }
        System.out.println(dp[D]);
    }
}