BOJ 14719 빗물

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

 

재밌는 문제였다. 문제를 낸 방식도 재밌고, 생각하는 것도 재밌었다.

처음 생각했던건  2차원 그래프를 그리면 어떨까 했다.

빈공간은 0, 벽은 1

그래서

0 0 1

1 0 1

1 1 1

뭐 이런식으로 해서 세어주는 식으로 하면 되지 않을까 싶었다.

그러면 어떻게 세어줘야 할까 생각하다가,

처음 벽이 세워지고 그 다음 벽이있는 곳까지의 개수를 세어주면 된다는 걸 알았고,

그렇다면 왼쪽에서 오른쪽으로 이동하는 걸 세면 되는데,

위에서부터 0이 될때까지 내려가면 된다는 걸 알았다.

그렇다면 굳이 2차원 배열을 만들 필요도 없이 왼쪽에서 오른쪽으로 가며, 왼쪽 수보다 작은 수의 개수를 세다가 큰수가 나오면 잠깐 멈추고 뭐 이런거를 생각했었다. 그러니깐 오큰수 문제와 비슷하지 않을까 생각이 들었다.

 

그렇다면 오큰수 문제는 스택을 이용해 풀었었으니깐, 이번에도 스택을 이용할까 생각했는데 

또 굳이 스택을 이용해주지 않아도 되겠다는 생각이 들었다. 어차피 개수만 세면 되니깐. (물론 스택을 이용해줘도 풀 수 있을 것 같다.)

그리고 범위를 보니 w,h가 둘다 1이상 500이하인데, 이러면 2중포문을 돌려도 500 * 500 = 250000이라는 괜찮은 시간복잡도가 나오기 때문에 2중포문을 돌려서 풀었다.

#include <bits/stdc++.h>
using namespace std;
int h, w;
int a[504];
int f;
int strt;
int main()
{
    cin >> h >> w;
    for (int i = 0; i < w; i++)
    {
        cin >> a[i];
        if (f == 0 && a[i] != 0)
        {
            f = a[i];
            strt = i;
        }
    }
    int total = 0;
    // for (int i = f; i >= 0; i--)
    // {
    //     // i = 물높이
    //     int tmp = 0;
    //     for (int j = strt; j < w; j++)
    //     {
    //         if (a[j] < i)
    //         {
    //             tmp++;
    //         }
    //         else if (a[j] >= i)
    //         {
    //             cout << "i : " << i << ", j : " << j << "\n";
    //             cout << "tmp : " << tmp << "\n";
    //             total += tmp;
    //             tmp = 0;
    //         }
    //     }
    // }

    for (int i = h; i >= 0; i--)
    {
        int tmp = 0;
        bool flag = false;
        for (int j = 0; j < w; j++)
        {
            if (flag == false && a[j] >= i)
            {
                flag = true;
            }
            else if (flag && a[j] < i)
            {
                tmp++;
            }
            else if (flag && a[j] >= i)
            {
                // flag = false;
                total += tmp;
                tmp = 0;
            }
        }
    }
    cout << total << "\n";
    return 0;
}

 

i는 물높이를 의미하고, 0이 될때까지 하나씩 빼며 진행한다.

처음에 물보다 높은게 있어야 가두는 걸 시작할 수 있기 때문에 물보다 높은게 나오는지를 찾고, 그 다음부터는 물보다 벽이 낮다면 경우의수를 +1 해준다. 그리고 벽이 물보다 높아진다면 이때까지 더한 경우의 수를 총합에다가 더해준다.

총합에다가 바로 안더해준 이유는 마지막까지 물높이보다 높은 벽이 안나올 수 있기 때문이다.

 

처음 풀때는 입력받을 때, 처음으로 벽의 높이가 0이 아닌 부분을 구해서 물높이를 그부분부터 -를 해주고, 벽 탐색도 그부분부터 시작하는 걸로 했었는데, 생각해보니

0 0 1 0 1

0 0 1 0 1

1  1  1 0 1

이런 경우를 못잡을 거 같다. (이건 문제를 풀때는 생각하지 못했다.)

 

첫번째 풀이가 틀리고 나니, 그냥 모든 경우의 수를 넣어줘보자 라는 생각으로 

물높이 시작을 h부터, 벽탐색은 0부터 시작하게 만들었고, 답을 맞출 수 있었다!!