백준 2073[자바] java 수도배관공사

문제 링크: https://www.acmicpc.net/problem/2073

2073번: 수도배관공사

▶문제

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

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

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

---

▶입력

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

---

▶출력

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

---

▶해설

DP문제입니다. 조건 먼저 살펴보겠습니다.

 

1. 수도관 길이는 강까지의 길이와 딱 맞아야 한다.

2. 구성된 파이프 용량 중 가장 적은 용량을 용량으로 설정한다.

3. 완성된 파이프들 중 가장 큰 용량을 구해야 한다.

 

문제를 접했을 때 이해가 어려웠는데 정리하자면 

 

1. 파이프는 한 번씩만 사용 가능하다.

2. 하나의 수도를 만들었을 때 그중 가장 작은 값의 파이프 용량이 용량으로 결정된다.

3. 최소 하나의 수도를 만들 수 있고 여러 개를 만들 수 있다.  그중 가장 큰 용량을 구해라.

 

풀이는 간단합니다. n의 설치 거리가 주어졌지고, 각 파이프의 길이와 용량을 l과 c라고 하겠습니다.

파이프들이 경우 만들 수 있는 범위는 l~n-l입니다. 

이해를 돕기 위해 n = 9 l = 3 c = 5로 하겠습니다.

0

1

2

3

4

5

6

7

8

9

파이프가 만들 수 있는 범위는 3~6입니다. 그 이유는 3일 때 l이 3이므로 3에서의 용량이 결국 c의 용량이 됩니다. 그 후 4는 기존에 있던 4의 용량 vs (기존에 있던 1의 용량과 c를 비교해서 작은 값이 용량이 되며) 큰 값이 됩니다. 

이런 식으로 진행한다면 점화식을 도출할 수 있습니다.

dp[j] = Math.max(dp[j],Math.min(dp[j-arr[i][0]],arr[i][1]));

전체 코드

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n, m;

        String[] s = br.readLine().split(" ");

        n = Integer.parseInt(s[0]);
        m = Integer.parseInt(s[1]);

        int[][]arr =new int [m][2];

        for(int i=0; i<m; i++){
            String[] s1 = br.readLine().split(" ");
            arr[i][0] = Integer.parseInt(s1[0]);
            arr[i][1] = Integer.parseInt(s1[1]);
        }

        int [] dp = new int[n+1];

        dp[0] = Integer.MAX_VALUE;
        for(int i=0; i<m; i++){
            for(int j=n; j>=arr[i][0]; j--){
                dp[j] = Math.max(dp[j],Math.min(dp[j-arr[i][0]],arr[i][1]));
            }
        }
        System.out.println(dp[n]);
    }
}