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

문제 링크 : [백준] 수조(1)(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. 각 높이별로 수조에 얼마나 물이 차는지 확인을 할 수 있지만, N이 5만이기 때문에, 높이별로 각각의 수조에 대해 부피를 구한다면 TLE이 됩니다.
2. 그렇다면 우리가 모든 높이별로 모든 수조를 매번 구할 필요가 있는지 생각해봅니다.
3. 모든 수조는 자신의 바닥 높이보다 크고, 자신의 꼭대기 높이보다 낮은 부분에서는 높이가 높아질 수록, 자신의 밑넓이 * (물의 높이-자신의 바닥의 높이) 만큼의 물을 담을 수 있습니다.
4. 그렇다면 높이를 인덱스로하는 1차원 배열에 아래와 같은 작업을 해줍니다.
   4-1. 자신의 바닥높이에 +밑바닥 넓이
   4-2. 자신의 꼭대기 높이에 -밑바닥 넓이
5. 눈치채신분들도 계시겠지만, 스위핑을 하기 위한 밑작업을 하여, 수면을 1~마지막까지 각 높이별로 훑으면서 각 높이별로 물의 부피를 누적합으로 구하면 됩니다.
6. 단 우리는 소수점 두자리까지 구해야 합니다.
7. 아래와 같은 방법으로 소수점 두자리까지 구하여 출력해주면 됩니다.
   7-1. 현재 높이까지의 물의 부피가 구하고자 하는 부피와 같다면 소수점 아래 값은 0이됩니다.
   7-2. 그렇지 않다면 소수점을 구해야합니다.
   7-3. 현재 남은 물의 부피 * 10 / 현재 확보된 밑면의 넓이를 해주면, 소수점 첫째 자리를 구할 수 있습니다.
   7-4. 마찬가지로, 7-3을 한번 더 하면, 소수점 둘째자리까지 구할 수 있으나, 셋째 자리에서 반올림 해야되기 때문에, 남은 수가 5보다 작은지를 확인하여 소수 둘째자리수를 보정해줍니다.

시간복잡도

O(H+N)

코드

#include<cstdio>
#define MAX 1040005
int cap[MAX];
int b, x, y, h, s, v, N, i, j, k;
bool ex;
int main() {
    scanf("%d", &N);
    for(i = 0; i < N; i++) {
        scanf("%d %d %d %d", &b, &h, &x, &y);
        v = x * y;
        cap[b] += v;
        cap[b + h] -= v;
    }
    scanf("%d", &v);
    for(i = 1; i < MAX; i++) {
        s += cap[i - 1];
        v -= s;
        if(v == 0) {
            printf("%d.00", i);
            return 0;
        }
        else if(v < 0) {
            v += s;
            i--;
            ex = true;
            break;
        }
    }
    if(!ex) {
        printf("OVERFLOW");
        return 0;
    }
    v *= 10;
    j = v / s;
    v = (v % s) * 10;
    if(v == 0) {
        printf("%d.%d", i, j);
        return 0;
    }
    k = v / s;
    v = (v % s) * 10;
    if(v == 0) {
        printf("%d.%d%d", i, j, k);
        return 0;
    }
    if(s * 5 <= v) {
        k++;
        if(k == 10) {
            k = 0;
            j++;
            if(j == 10) {
                j = 0;
                i++;
            }
        }
    }
    printf("%d.%d%d\n", i, j, k);
}