[백준] 2073 수도배관공사 - Java

 

 

 

문제 출저

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

 

 

 

문제 풀이

파이프를 선택하여 길이 d인 파이프를 만들려 합니다. 파이프는 길이와 용량이 주어집니다. 전체 파이프의 용량은 가장 작은 용량이 됩니다. 이 때, 용량이 가장 클 때를 구해야 합니다. 

 

 

dp, 배낭 문제로 문제를 풀었습니다. 

전체 용량이 가장 큰 경우를 구해야 합니다. 

 

파이프(길이 : l, 용량 : c)

전체 길이를 d로 봤을 때 각각의 파이프 경우마다 전체 길이 d부터 현재 탐색하는 파이프의 길이 l까지 탐색합니다.  
이미 있는 파이프의 용량(dp[j-l])과 현재 탐색하는 중인 파이프의 용량(c)을 비교하여 더 작은 것을 선택합니다.

이것을 기존에 용량(dp[j])와 비교하여 더 큰 것을 dp[j]에 저장하여 정답을 구합니다. 

 

 

 

소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

/*
수도 배관 공사
https://www.acmicpc.net/problem/2073

파이프(길이 : l, 용량 : c)
이미 있는 파이프의 용량(dp[j-l])과 현재 탐색하는 중인 파이프의 용량(c)을
비교하여 더 작은 것을 선택한다.

이것을 기존에 용량(dp[j])와 비교하여 더 큰 것을 dp[j]에 저장한다.

 */

public class Main {

    static int d; // 거리
    static int p; // 파이프 종류
    static int[] dp;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        d = Integer.parseInt(st.nextToken());
        p = Integer.parseInt(st.nextToken());

        dp = new int[d + 1];
        dp[0] = Integer.MAX_VALUE;

        while (p-- > 0) {
            st = new StringTokenizer(br.readLine());
            int l = Integer.parseInt(st.nextToken()); // 길이
            int c = Integer.parseInt(st.nextToken()); // 용량

            for (int i = d; i >= l; i--) {
                dp[i] = Math.max(dp[i], Math.min(dp[i-l], c));
            }
        }

        System.out.println(dp[d]);

    }

}