[백준] 수조(2)(2130)

문제 링크 : [백준] 수조(2)(2130)

문제 설명

문제 설명이 어려우니 링크 참조 해주세요.

입력

N(수조의 갯수,1<=N<=50,000)
B_i(수조가 위치한 높이,0<=B_i<=1,000,000)
H_i(수조 자체의 높이,1<=H_i<=40,000)
W_i(수조의 가로 길이,1<=W_i<=40,000)
D_i(수조의 세로 길이,1<=D_i<=40,000)
V(물의 부피,1<=2,000,000,000)

4
11 7 5 1
15 6 4 1
5 8 5 1
19 4 8 1
78

출력

수면의 높이

17.00

카테고리

#이분탐색

시간 복잡도 상한

W,D는 수조의 면적을 구하기 위한 것으로 문제를 푸는 시간 복잡도에는 영향을 주지 않을 것 같습니다.
밑면부터 수조의 꼭대기가 위치할 수 있는 최대 높이까지 각 높이별로 물의 부피를 구한다면,
1,040,000 * 50,000 이므로 TLE가 됩니다.
대략 O(Nlog(B+H)) 정도가 상한이 될 것 같습니다.

해결 방법

1. 앞서 스위핑과 누적합으로 푸는 방법을 살펴봤습니다만, 다른 방법으로도 풀 수 있습니다.
2. N이 5만이고, H가 1,040,000이기 때문에 시간복잡도 상한에서 살펴봤듯이, O(NlogH)에도 풀 수 있습니다.
3. 즉, 높이를 반씩 잘라가면서 각 수조별로 물이 차는 부피를 구해도 문제를 풀 수 있다는 얘기가 됩니다.
4. 따라서 높이를 기준으로 이분탐색을 하면서, 적당한 높이를 만날 때 까지, 이분탐색으로 정답을 구할 수 있습니다.
5. 이분탐색이 가능함을 확인하는 방법은 아래와 같습니다.
   5-1. 높이가 높아 질수록, 수조에 담기는 물의 부피는 절대 작아지지 않습니다.(비내림차순)
   5-2. 5-1의 조건에 의해 기준이 되는 높이에서의 물의 부피가 찾고자하는 부피보다 작다면, 높이를 높이고, 그렇지 않다면 높이를 낮추는 방식으로 찾을 수 있습니다.
6. 하지만 문제가 있습니다.
7. 일반적인 이분탐색(파라메트릭 서치)은 답이 정수일 때만 가능합니다.
8. 하지만 이분탐색을 다시 생각해본다면, 이분탐색이 정수만 가능한 이유는, 종료 조건이 l과 r의 관계가 같아지거나, 대소가 역전이 되는 경우까지 찾습니다.
9. 여기서 이분탐색의 기능에 대해 다시 생각해봅니다.
10. 이분탐색을 8과 같이 사용하는 이유는 우리가 일반적으로 정수 범위에서 사용하므로 이해하기, 구현하기 편하게 생각해서 그렇다고 봅니다.
11. 실제로 이분탐색은 연산 한번에 정확도가 두배 증가한다고 보는 것이 더 정확할 것입니다.
12. 범위가 2¹⁰이었다면, 한번의 연산으로 정확도는 2⁹, 두번의 연산으로는 2⁸이 될 겁니다.
13. 즉, 연산 한번에 범위가 반씩 줄어듭니다.
14. H가 최대 1,040,000 이므로, 대략 20번이면 정수범위까지는 정확한 값을 찾을 수 있습니다.
15. 여기서 l과 r을 소수범위까지 탐색하면서 대략 10번을 더하면 1/2¹⁰의 오차까지 범위를 줄일 수 있을 겁니다.
16. 대략 이분탐색을 30번 반복하며, 각 높이별로, 수조들을 순회하면서 수조별 물의 부피를 구해 결정함수의 값을 확인하여 l과 r을 조정하면서 답을 구할 수 있습니다.

시간복잡도

O(NlogH)

코드

import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

public class Main {
    public static int N, V;
    public static float ANSWER;
    public static Node[] INPUTBOX = new Node[50000];

    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);

        N = sc.nextInt();
        Node[] BOX = Arrays.copyOf(INPUTBOX, N);
        int highest = 0;
        for(int i=0;i<N;i++){
            Node node = new Node();
            node.b = sc.nextInt();
            node.h = sc.nextInt();
            node.w = sc.nextInt();
            node.d = sc.nextInt();
            BOX[i]=node;
            if(highest < node.b+node.h) {
                highest = node.b+node.h;
            }
        }
        V = sc.nextInt();

        Arrays.sort(BOX, new Comparator<Node>() {
            @Override
            public
            int compare(Node a, Node b){
                return a.b - b.b;
            }
        });

        double min = BOX[0].b;
        double max = highest+1;

        if(getSize(BOX, highest) < V) {
            System.out.println("OVERFLOW");
            return;
        }
        double mid = 0;
        for(int i=0;i<50;i++){
            mid = (max-min)/2 + min;

            double volume = getSize(BOX, mid);

            if(volume >= V) {
                max = mid;
            }else if(volume < V) {
                min = mid;
            }
        }

        System.out.format("%.2f%n", mid);
    }

    public static double getSize(Node[] BOX, double mid) {
        double volume = 0;
        for(int i=0;i<N;i++){
            if(mid>=BOX[i].b+BOX[i].h) {
                volume += BOX[i].w*BOX[i].d*BOX[i].h;
            }else if(mid<BOX[i].h+BOX[i].b && mid > BOX[i].b) {
                volume += BOX[i].w*BOX[i].d*(BOX[i].h-(BOX[i].h+BOX[i].b-mid));
            }
        }
        return volume;
    }

    public static class Node {
        public int b,h,w,d; 
    }
}