[백준] 14719 빗물

 

문제 설명을 잘 읽어보자.

https://www.acmicpc.net/problem/14719

14719번: 빗물

 

빗물이 고이는 특성은 다음과 같다.

1. 좌측 끝과 우측 끝이 벽으로 막혀 있어야 한다.

2. 빗물이 찼을 때 양쪽 끝이 같다.

3. 중간에 구멍이 생길 일은 전혀 없다. (주어진 조건이 밑에서부터 위로 몇 칸 있는지 확인하므로)

 

이러한 특징을 기반으로 다음과 같은 풀이 알고리즘을 생각해 보았다.

1. 수면의 높이가 1~N 일때까지 탐색한다.

2. 물이 있는 시작점은 현재 탐색 칸이 벽이고, 탐색 다음칸은 물이다.

3. 물이 있는 끝점은 현재 탐색 칸이 물이고, 탐색 다음칸은 벽이다.

4. 혹시나 마지막 탐색 시 벽이 뚫려 있으면, 물이 고여 있지 않는다.

 

위의 조건을 바탕으로 구현을 해 보았다. 수면의 높이는 사각형의 윗변의 높이를 기준으로 탐색한다. 탐색방향은 아래에서 위로, 왼쪽에서 오른쪽으로 탐색을 진행하며 한번에 한 층의 조건만 탐색을 진행한다.

 

결과 코드는 다음과 같다.

 

#include <iostream>
#include <cstring>
using namespace std;
 
int block[501];
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    int h, w, ans = 0, temp, isWater;
    cin >> h >> w;
    for (int i = 0; i < w; i++)
        cin >> block[i];
    for (int dep = 1; dep <= h; dep++)
    {
        isWater = 0;
        temp = 0;
        for (int i = 0; i < w - 1; i++)
        {
            if (isWater)
            {
                ans++;
                temp++;
            }
            if ((block[i] - dep >= 0) && (block[i + 1] - dep < 0))
                isWater = 1;
            if ((block[i] - dep < 0) && (block[i + 1] - dep >= 0))
            {
                isWater = 0;
                temp = 0;
            }
        }
        ans -= temp;
    }
    cout << ans;
}