백준 2073번 수도배관공사

문제

나의 풀이

import java.util.Scanner;

// 2073번 수도배관공사
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int d = sc.nextInt(); // 만들어야 될 수도관의 길이
        int p = sc.nextInt(); // 파이프의 개수
        int dy[] = new int[d + 1]; // 다이나믹 테이블 생성
        for(int i = 0; i < p; i++) { // 파이프들을 탐색
            int l = sc.nextInt(); // 파이프 길이
            int c = sc.nextInt(); // 파이프 용량

            // 다이나믹 적용
            for(int j = d; j > l; j--) { // 만들어야될 수도관의 길이부터 현재 파이프 길이의 바로 전까지만 반복하기 (뒤에서부터 해야 중복 사용 방지 가능)
                if(dy[j - l] == 0) { // 현재 탐색중인 j라는 길이에서 현재 파이프의 길이를 뺐을 때 0인 경우
                    continue; // (j-l)수도관은 만들어있지 않으니까 현재 파이프를 사용해서 값을 구하지 못한다는 말이므로 건너뛰기
                }
                dy[j] = Math.max(dy[j], Math.min(dy[j - l], c)); // (j-l)길이의 수도관 용량과 현재 파이프 용량 중에서의 최소값과 j길이의 수도관 용량 중 최대값을 dy[j]로 업데이트
            }
            // l전까지 돌았으므로 마지막은 l길이의 수도관 용량도 정해주기
            dy[l] = Math.max(dy[l], c); // l길이인 현재 파이프를 사용한 용량과 기존 l길이의 수도관의 용량 중 최대값으로 업데이트 해주기
        }
        System.out.println(dy[d]); // 최종적으로 d길이의 수도관 용량을 출력해주기 
    }
}

P의 개수가 350이하로 많기 때문에 BFS를 이용해서 부분집합으로 풀면 안되고 DP를 이용해야 한다. 냅색 다이나믹을 이용한다. dy[i]는 i 길이의 수도관을 만들었을 때 최대 용량을 의미한다. 파이프의 개수가 각각 한개씩이기 때문에 dy 테이블을 앞에서부터가 아닌 뒤에서부터 적용해서 중복적용되지 않게 해야 한다. D에서부터 현재 파이프의 길이까지 뒤에서부터 탐색하면서 dy[i]값과 현재 파이프를 적용했을 때의 용량값 중 큰값으로 업데이트 해준다. 이때 dy[i - 현재파이프 길이] 값이 0이면 현재파이프와 (i-파이프길이) 파이프를 사용하여 i길이의 수도관을 만들 수 없다는 뜻이므로 넘어간다. 만약 dy[i-현재파이프길이]의 값이 0이 아닌 경우 최소값(dy[i-현재파이프의길이], 현재파이프 용량)과 dy[i] 값 중 큰값으로 dy[i]를 업데이트 해준다. 하지만, i가 현재 파이프의 길이인 경우 dy[i-현재파이프의길이] 값을 비교하는 게 아닌 dy[현재파이프의길이]값과 현재파이프의길이 용량 중 최대값으로 업데이트 해준다. 끝나고 나면 dy[D] 값을 리턴해주면 된다.

결과