[골드4] 백준 2073번 '수도배관공사' (이분탐색으로도 풀리더라)

이 문제는 DP로 푼 사람들이 많다. 그런데 나는 이분탐색이 떠올라서 이분탐색으로 풀었다. 혹시나 나처럼 이분탐색으로 접근한 사람이 있다면 참고가 되길 바라며 작성한다.

'수도배관공사' 문제 바로가기

왜 이분탐색이라고 생각했는가?
1. 처음에는 길이와 용량의 범위가 크다고 생각했다.
(지금 보니 별로 안크긴 함. 2^23 = 8,388,608. 다음에는 계산을 잘 해야겠다)
2. mid 값과 부분조합을 잘 섞으면 될 것 같았다.

접근 방법

1. 용량별로 정렬
2. mid : 최소 용량
3. left : 양의 정수 최솟값 1, right : 가장 큰 용량
4. mid 이상의 용량인 파이프들로 길이 D를 만들 수 있는지 확인(부분집합 사용)
5. 길이 D를 만들 수 있으면 정답 갱신. mid의 최대값을 구해야하므로 left 증가시킴
   • D를 만들 수 없으면 조합에 더 많은 요소들이 필요함. right 감소시켜서 더 많은 파이프를 조합에 활용할 수 있게 함.

정답 코드

• 참고로 부분집합을 계산하는 subset 함수의 path 파라메터는 디버깅시 확인용이었다. 없어도 된다.

public class Main {
    static long D;
    static int P;
    static long[][] pipes;
    static boolean[] visit;
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        D = sc.nextLong();
        P = sc.nextInt();
        pipes = new long[P][2];
        visit = new boolean[P];
        
        for(int i = 0; i < P; i++) {
            pipes[i][0] = sc.nextLong(); //길이
            pipes[i][1] = sc.nextLong(); //용량
        }
        Arrays.sort(pipes, (a, b) -> a[1]!=b[1] ? Long.compare(a[1], b[1]) : Long.compare(a[0], b[0]));

        long left = 1;
        long right = pipes[P-1][1];
        long answer = 1;
        while(left <= right) {
            long mid = (left+right)/2;
            
            boolean making = false;
            int start = 0;
            for(int i = 0; i < P; i++) {
                if(pipes[i][1] >= mid) {
                    start = i;
                    int size = P-start; // 부분집합 크기
                    making = subset(size, 0, 0, start, new long[size]);
                    break;
                }
            }
            
            if(making) {
                left = mid + 1;
                answer = mid;
            } else {
                right = mid - 1;
            }
        }
        
        System.out.print(answer);
        sc.close();
    }
    
    private static boolean subset(int m, int cnt, long sum, int i, long[] path) {
        if(cnt == m || i == P || sum >= D) {
            if(sum == D) {
                return true;
            }
            return false;
        }
        
        if(subset(m, cnt, sum, i+1, path)) return true;
        
        path[cnt] = pipes[i][0];
        if(subset(m, cnt+1, sum+pipes[i][0], i+1, path)) return true;
        path[cnt] = 0;

        return false;
    }
}