[JAVA]백준 2073번: 수도배관공사

www.acmicpc.net/problem/2073

2073번: 수도배관공사

 

1. 문제 설명

 

각 마을별로 파이프의 길이와 용량이 주어질 때, 수도관의 용량은 그것을 이루는 파이프들의 용량 중 최솟값이 된다고 하자. 파이프 길이의 총합이 수도관의 길이와 정확히 같을 때, 가능한 최대 수도관 용량을 구하는 문제이다.

 

2. 풀이

 

dp [y]=수도관의 길이가 y일 때 최대 수도관 용량

= Math.max(dp[y],Math.min(dp[y-length],capacity))

 

수도관의 용량은 그것을 이루는 파이프들의 용량 중 최솟값이기에 만약 현재 입력받은 마을의 파이프를 사용한다고 하면 (파이프의 길이는 length, 용량은 capacity라고 하자) dp [y-length]와 capacity 중 최솟값을 가질 것이다. 

문제에서 요구하는 것은 최대 수도관의 용량을 구하는 것이기에 파이프를 사용하는 것과 사용하지 않은 것 중 최댓값을 저장하면 된다. 

 

3. 코드

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));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int distance, town;
        int MAX = 33554432;

        StringTokenizer input = new StringTokenizer(br.readLine());

        distance = Integer.parseInt(input.nextToken());
        town = Integer.parseInt(input.nextToken());

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

        dp[0] = MAX;

        for (int x = 0; x < town; x++) {
            int length, capacity;

            StringTokenizer pipe = new StringTokenizer(br.readLine());

            length = Integer.parseInt(pipe.nextToken());
            capacity = Integer.parseInt(pipe.nextToken());

            for (int y = distance; y >= length; y--) {
                dp[y] = Math.max(dp[y], Math.min(capacity, dp[y - length]));
            }

        }

        bw.write(String.valueOf(dp[distance]) + "\n");
        bw.flush();
        bw.close();
        br.close();

    }



}