[Simulation] 백준 14719: 빗물

14719번: 빗물 (acmicpc.net)

 

처음에는 각 column 간의 차이를 위주로 접근하다가, 위에서부터 한 row씩 훑고 내려오면서 연산하는 방식으로 접근을 달리했다.

 

맨 위 row 부터 순회하면서, 만일 값이 1인 칸을 이미 만난 상태라면 이후 0인 칸을 만날 때마다 값을 더해준다. 만일 다시 값이 1인 칸을 만나면, 해당 값을 정답에 더해주고 0으로 초기화한다.

 

양 옆이 뚫려 있다고 생각해야 하므로, 다음 row로 내려갈 때 값을 0으로 초기화한다. 이 때 1인 칸을 만났는지 여부를 확인하는 flag(여기서는 isFill)을 false로 초기화 해 준다.

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int W, H;
    cin>>H>>W;

    vector<vector<int>> board(H, vector<int>(W));

    int input;
    for(int i=0;i<W;i++)
    {
        cin>>input;
        for(int j=0;j<input;j++)
        {
            board[j][i] = 1;
        }
    }
    int tmp = 0;
    int ans = 0;
    bool isFill = false;

    for(int r=H-1;r>=0;r--)
    {
        for(int c=0;c<W;c++)
        {
            if(board[r][c]==0)
            {
                if(isFill) tmp++;
            }
            else if(board[r][c]==1)
            {
                if(isFill)
                {
                    ans+=tmp;
                    tmp = 0;
                }
                else{
                    isFill = true;
                }
            }

            if(c==W-1)
            {
                isFill = false;
                tmp = 0;
            }
        }
    }

    cout<<ans;
}