[c++] 백준 8985 수족관 2

백준 8985 수족관 2

8985번: 수족관 2

문제를 만나고 나서 생각을 시작해 보면 금방 발견할 수 있는 것이 있다.

계산을 할 구간의 최소 높이가 존재하는 곳을 기준으로 부분 부분 나뉘어 각각의 연산을 다시 실행한다는 것

이러한 특징을 찾으면 바로 분할 정복임을 눈치챌 수 있을 것이다.

 

그러면 문뜩 머릿속에 그럼 물이 빠져나가는 시간은 어떻게 구하지? 가 떠오른다

분할된 구간에서 물은 얼만큼 빠져나가고 시간은 얼만큼 걸리는가.

분할됐을 때의 높이에서 분할되기 직전 즉, 구간의 최소 높이까지 물이 빠져나간다.

 

그림을 예시로 들면

분할됐을 때의 높이(초기 상태니까 0)에서

구간의 최소 높이(2)까지 물이 빠져나간다

이제 대략적인 문제의 해결 방법을 알았다.

다음은 문제를 해결할 때 필요한 값들을 어떻게 구할 것인가인데

구해야 할 값들은 다음과 같다.

 

1. 구간의 최소 높이

분할 정복을 위해 구간의 최소 높이가 존재하는 위치(index값)를 알아야 한다.

구간의 최소 높이의 위치를 알기 위해 세그먼트 트리를 사용할 것이다.

세그먼트 트리에는 구간에서의 최솟값 위치를 저장한다.

 

2. 구간의 구멍의 개수

물이 빠져나가는 시간을 구하기 위해 구멍의 개수가 필요하다.

구멍의 개수를 알기 위해 누적합을 사용할 것이다.

구멍을 가지고 있는 가로선의 인덱스에 1을 입력 후 누적한다.

 

3. 처리하기 쉬운 데이터로 입력 바꿔주기

문제에서 입력이 좌표로 주어진다.

이는 상당히 복잡하고 알아보기 힘들기 때문에 전처리를 해주자.

이건 자신이 편한 대로 요령껏 해주면 된다.

나는 새로운 가로선이 나올 때마다 새로운 인덱스를 할당하고, 그 높이를 저장했다.

그리고 가로길이를 알기 위해 그 선분의 좌표를 저장했다.

 

문제를 풀기 위해 필요한 준비물이 다 갖추어졌다.

이제 분할 정복의 방법에 대해 생각해 보자.

 

매개변수로 구간을 받고, 이전 구간이 나뉘기 전의 최소 높이를 받는다.

그러고 나서 필요한 값은 두 가지이다.

구간의 최솟값의 위치와, 구간의 구멍의 개수.

 

구간의 구멍의 개수에 따라 상황이 나누어진다는 것을 알 수 있다.

1. 물이 빠져나갈 때

2. 물이 빠져나가지 않을 때

if문으로 구멍이 있을 때 없을 때를 나누어주자.

 

1. 물이 빠져나갈 때

위에서 언급한 물이 빠져나갈 부피에서 구멍의 개수를 나눈 것이 물이 빠져나가는 시간이 된다.

최솟값 인덱스를 기준으로 구간을 나누어주자.

구간을 나누고 각각의 구간에서 동시에 물이 빠져나가므로

나눈 구간의 return값 중 최대와 앞에서 구한 물이 빠져나가는 시간을 더해 return 해주자.

2. 물이 빠져나가지 않을 때

이때는 물의 양이 줄지 않는다.

따라서 수조에 남아있는 물의 양을 구해준다.

전역 변수에 더해주자.

 

※주의사항

자료형을 주의하자. double도 있고 long long도 사용해야 하기에

자료형에서 실수할 수도 있다.

(여기서 시간 엄청 날림...)

 

정답 코드

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<pair<ll,ll>,pair<ll,ll>> pppp;
#define N 300300
#define F first
#define S second
pppp spot[N];
ll arr[N];
ll n,k,ans,x,y,idx,ba;
ll pre[N],sg[N*4];
ll min_idx(ll p, ll q){
    p += ba, q += ba;
    ll v = 1e9,vi;
    while(p<q){
        if(p%2 == 1){
            if(v > arr[sg[p]])
                v = arr[sg[p]], vi = sg[p];
            p++;
        }
        if(q%2 == 0){
            if(v > arr[sg[q]])
                v = arr[sg[q]], vi = sg[q];
            q--;
        }
        p/=2, q/=2;
    }
    if(p == q && v > arr[sg[p]])
        vi = sg[p];
    return vi;
}
void update(ll p, ll q){
    p += ba; sg[p] = q;
    for(p/=2; p>0; p/=2)
        sg[p] = arr[sg[p*2]]<arr[sg[p*2+1]] ? sg[p*2]:sg[p*2+1];
}
void preprocess(){
    cin>>n>>x>>y;
    for(ll i=1; i<n; i++){
        ll a,b; cin>>a>>b;
        if(a == x) y = b;
        else{
            arr[idx] = y;
            spot[idx++] = {{x,y},{a,y}};
            x = a;
        }
    }
    cin>>k;
    for(ll i=0; i<k; i++){
        ll a,b,c,d; cin>>a>>b>>c>>d;
        ll j = lower_bound(spot,spot+idx,make_pair(make_pair(a,b),make_pair(c,d)))-spot;
        pre[j]++;
    }
    for(ll i=1; i<idx; i++)
        pre[i] += pre[i-1];
    for(ba=1; ba<idx; ba*=2);
    for(ll i=0; i<idx; i++)
        update(i,i);
}
double divide(ll l, ll r, ll h){
    if(l > r) return 0;
    ll m = min_idx(l,r);
    ll ana_num = pre[r];
    if(l != 0) ana_num -= pre[l-1];
    if(ana_num == 0){
        for(ll i=l; i<=r; i++)
            ans += (arr[i]-h)*(spot[i].S.F-spot[i].F.F);
        return 0;
    }
    else{
        double tmp = max(divide(l,m-1,arr[m]),divide(m+1,r,arr[m]));
        double w = (arr[m]-h)*(spot[r].S.F-spot[l].F.F);
        return (w/(double)ana_num)+tmp;
    }
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    preprocess();
    cout << fixed;
    cout.precision(2);
    cout << divide(0,idx-1,0) << '\n' << ans;
    return 0;
}