수족관

작성일 | In

[백준] 8982번 - 수족관

문제 링크

KOI 2013 초등부 문제.
특별한 알고리즘을 사용해야 하는 문제는 아니었다. 시뮬레이션 문제이다.

개인적으로 이런 시뮬레이션 문제가 너무 어렵게 느껴진다.
이에 아래 포스트를 참고하여 문제 해결 아이디어를 얻었다.
알고리즘을 열심히 공부해도 구현력이 뒷받쳐주지 못하면 소용 없다는 느낌을 강하게 느꼈다.
들짐승 님의 블로그

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <bits/stdc++.h>
using namespace std;

vector<int> sink; // 구멍 수평선분 x좌표 저장
vector<int> startHeight; // 각 x좌표의 물 깊이
vector<int> height; // 각 x좌표의 깊이(y좌표)
int horiz; // 수평선분 개수

int main(void) {
    int n;
    scanf("%d", &n);

    pair<int, int> post = {0,0};
    pair<int, int> cur;
    for(int i=0; i<n; ++i) {
        scanf("%d %d", &cur.first, &cur.second);
        // 수평선분
        if(cur.first != post.first) {
            for(int j=post.first; j<cur.first; ++j)
                height.push_back(post.second);
        }
        post = cur;
    }
    startHeight.resize(height.size(), 0);

    int s;
    scanf("%d", &s);
    for(int i=0; i<s; ++i) {
        int sx,sy,ex,ey;
        scanf("%d %d %d %d", &sx, &sy, &ex, &ey);
        sink.push_back(sx);
    }

    horiz = height.size();
    for(int i=0; i<sink.size(); ++i) {
        int h = height[sink[i]];
        startHeight[sink[i]] = h;
        // 좌 갱신
        for(int j=sink[i]-1; j>=0; --j) {
            if(h > height[j])
                h = height[j];
            if(h > startHeight[j])
                startHeight[j] = h;
        }

        // 우 갱신
        h = height[sink[i]];    
        for(int j=sink[i]+1; j<horiz; ++j) {
            if(h > height[j])
                h = height[j];
            if(h > startHeight[j])
                startHeight[j] = h;
        }
    }

    int ans=0;
    for(int i=0; i<horiz; ++i)
        ans += height[i] - startHeight[i];

    printf("%d", ans);
}
0%