[자바로 푸는 백준] 2073번 수도배관공사

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

2073번: 수도배관공사

✅ 골드 Ⅳ

 

🔶 풀이

해당 문제는 다이나믹 프로그래밍(dp)로 문제의 조건은 아래와 같다.

 

1️⃣ 파이프는 하나씩 사용이 가능하고, 수도배관 길이는 강까지의 거리(D)와 동일해야 한다.

2️⃣ 수도배관을 완성했을 경우, 가장 적은 용량을 가진 파이프가 해당 수도배관의 용량이다.

3️⃣ 동일한 길이를 가진 여러 개의 수도배관 중에 가장 큰 용량을 구하라.

 

 

파이프의 길이를 정확하게 강까지의 거리(D)와 동일해야 하므로 dp배열을 D부터 진행한다.

for (int j=D; j>=L; j--) {
    dp[j] = Math.max(dp[j], Math.min(C, dp[j-L]));
}

파이프 길이를 4라고 가정했을 때, 정확하게 D를 만들 수 있는 경우의 수는 4부터 D까지다. 때문에 D부터 -1씩 해주면서 위와 같은 방법으로 진행해 줬다.

 

하지만 위와 같은 방법으로만 진행해 주면 3️⃣번 조건이 생략된다. dp[0]이 0으로 선언되어 있기 때문에 아무리 반복문을 돌려도 Math.min(C, dp[j-L])에서 모두 0이 나올 것이다. 

dp[0] = Integer.MAX_VALUE;

dp[0]을 위처럼 선언해 줌으로써 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));
        StringTokenizer st = new StringTokenizer(br.readLine());
		
        int D = Integer.parseInt(st.nextToken()); // 강까지의 거리
        int P = Integer.parseInt(st.nextToken()); // 파이프 개수

        int[] dp = new int[D+1];
		
        dp[0] = Integer.MAX_VALUE;
		
        for (int i=0; i<P; i++) {
            st = new StringTokenizer(br.readLine());
			
            int L = Integer.parseInt(st.nextToken()); // 길이
            int C = Integer.parseInt(st.nextToken()); // 용량
			
            for (int j=D; j>=L; j--) {
                dp[j] = Math.max(dp[j], Math.min(C, dp[j-L]));
            }
        }
		
        System.out.println(dp[D]);
    }
}