[백준 8982번] 수족관 1 (C++)

문제링크 : https://www.acmicpc.net/problem/8982

8982번: 수족관 1

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MAX 987654321
#define pii pair <int, int>

pii depth[400001]; //각 최대 깊이와 빠져나간 깊이

int main()
{
    int N, M, result = 0;
    cin >> N;

    int x1, y1, x2, y2;
    cin >> x1 >> y1; //0, 0 (시작점)
    for(int i=0; i<N/2-1; i++)
    {
        cin >> x1 >> y1 >> x2 >> y2;
        for(int j=x1; j<x2; j++)
        {
            depth[j].first = y1; //해당 위치에 따른 깊이 저장
        }
    }
    cin >> x1 >> y1; //x, 0 (끝점)
    
    int width = x1; //가로길이 저장

    vector<int> hole; //구멍 갯수 담기

    cin >> M;
    for(int i=0; i<M; i++)
    {
        cin >> x1 >> y1 >> x2 >> y2;
        hole.push_back(x1); //구멍 위치
    }

    for(int i=0; i<hole.size(); i++)
    {
        int d = depth[hole[i]].first; //현재 구멍의 깊이
        depth[hole[i]].second = d;

        for(int j=hole[i]-1; j>=0; j--) //구멍의 왼쪽
        {
            d = min(d, depth[j].first); //이 이상으로 못 깊어짐 (표면)
            depth[j].second = max(depth[j].second, d); //뺄수 있는 최대 깊이 
        }
        d = depth[hole[i]].first;

        for(int k=hole[i]+1; k<width; k++) //구멍의 오른쪽
        {
            d = min(d, depth[k].first); //이 이상으로 못 깊어짐 (표면)
            depth[k].second = max(depth[k].second, d); //뺄수 있는 최대 깊이 
        }

    }

    for(int i=0; i<width; i++)
    {
        result += (depth[i].first - depth[i].second); //최대 깊이 - 빠져나간 깊이
    }

    cout << result;
}

구멍을 기준으로 좌우를 탐색해준다.

기존에 해당 x좌표에 따른 깊이를 저장해준 것을 이용하여 현재 구멍의 깊이와 구멍의 왼쪽에 있는 깊이, 구멍의 오른쪽에 있는 깊이를 각각 비교하여 뺄 수 있는 최대 깊이를 구해준다.

 

아직 골드3 문제도 온전히 나만의 힘으로 풀기는 버거운 것 같다.

어느정도 아이디어는 잡을 수 있지만, 아직 구현이 부족한 것 같다.