[Baekjoon] 빗물

👀 문제 설명

문제

2차원 세계에 블록이 쌓여있다. 비가 오면 블록 사이에 빗물이 고인다.

비는 충분히 많이 온다. 고이는 빗물의 총량은 얼마일까?

 

입력

첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500)

두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치부터 차례대로 W개 주어진다.

따라서 블록 내부의 빈 공간이 생길 수 없다. 또 2차원 세계의 바닥은 항상 막혀있다고 가정하여도 좋다.

 

출력

2차원 세계에서는 한 칸의 용량은 1이다. 고이는 빗물의 총량을 출력하여라.

빗물이 전혀 고이지 않을 경우 0을 출력하여라.

 

예제 입력 1

4 4

3 0 1 4

 

예제 출력 1

5

 

예제 입력 2

4 8

3 1 2 3 4 1 1 2

 

예제 출력 2

5

 

예제 입력 3

3 5

0 0 0 2 0

 

예제 출력 3

0

 

✍🏻풀이

이전에 풀었던 문제인데, 소희가 알려준 방법으로 다시 풀어봤다.

 

1. 먼저, 블록들 중 가장 높은 블록을 찾아 블록의 높이(maxBlock)와 해당 블록의 인덱스(maxBlockIndex)를 저장한다.

그리고, maxBlockIndex 기준 왼쪽과 오른쪽 블록들을 접근하며 고이는 양을 계산해주면 된다.

 

2-1. 왼쪽 블록들 중, 가장 높은 블록(leftMax)과 다른 블록들의 차이를 계산해서 더해주면 된다.

먼저, leftMax의 초기값을 가장 왼쪽에 있는(인덱스 0인) 블록의 높이로 설정하고, 다음 블록들과의 차이를 구한다.

만약, 어떤 인덱스의 블록이 leftMax보다 작으면, leftMax와 해당 블록의 차이를 구해, answer에 더한다. (그만큼 고이기 때문에)

만약, 어떤 인덱스에 있는 블록이 leftMax보다 크다면, leftMax를 해당 블록으로 바꿔준다.

 

2-2. 오른쪽 블록들 중, 가장 높은 블록(rightMax)과 다른 블록들의 차이를 계산해서 더해준다.

먼저, rightMax의 초기값을 가장 오른쪽에 있는(인덱스 W - 1인) 블록의 높이로 설정하고, 다음 블록들과의 차이를 구한다.

만약, 어떤 인덱스의 블록이 rightMax보다 작으면, rightMax와 해당 블록의 차이를 구해, answer에 더한다. (그만큼 고이기 때문에)

만약, 어떤 인덱스에 있는 블록이 rightMax보다 크다면, rightMax를 해당 블록으로 바꿔준다.

 

코드

//
//  BOJ_14719_again.cpp
//  Algorithm
//
//  Created by 조수민 on 2021/03/23.
//  Copyright © 2021 조수민. All rights reserved.
//
//  빗물(https://www.acmicpc.net/problem/14719)

#include <stdio.h>
#include <iostream>
#include <vector>

using namespace std;

int H, W;
vector<int> blocks;

/**
 1. 제일 높은 블록 찾기
 2-1. 제일 높은 블록 기준 왼쪽에서 제일 높은 걸 찾고(max1), max1과 왼쪽 블록들의 차이?가 고인다?
 2-2. 제일 높은 블록 기준 오른쪽에서 제일 높은 걸 찾고(max2), max2와 오른쪽 블록들의 차이
 */
int main() {
    ios::sync_with_stdio(0);
    cin.tie(NULL); cout.tie(NULL);
    
    // input
    cin >> H >> W;
    blocks.resize(W);
    
    int maxBlock = 0;
    int maxBlockIndex = -1;
    
    for (int i = 0; i < W; i++) {
        cin >> blocks.at(i);
        // 1. 제일 높은 블록 찾기
        if (maxBlock < blocks.at(i)) {
            maxBlock = blocks.at(i);
            maxBlockIndex = i;
        }
    }
    
    int answer = 0;
    // 2. 제일 높은 블록 기준 왼쪽
    int leftMax = blocks.at(0); // 초기값은 0번째 있는 애로 정한다.
    for (int i = 1; i <= maxBlockIndex; i++) { // 1부터 maxBlockIndex까지
        if (leftMax != 0 && blocks.at(i) < leftMax) { // 현재 위치의 블록이 leftMax보다 작을 경우
            answer += leftMax - blocks.at(i);
        }
        if (leftMax <= blocks.at(i)) { // 현재 위치의 블록이 leftMax보다 크거나 같을 경우
            leftMax = blocks.at(i); // leftMax를 현재 위치의 블록으로 바꿔준다.
        }
    }

    // 3. 제일 높은 블록 기준 오른쪽
    int rightMax = blocks.at(blocks.size() - 1); // 초기값은 w - 1로 설정한다 (제일 오른쪽에 있는 애)
    for (int i = blocks.size() - 2; i >= maxBlockIndex; i--) {
        if (rightMax != 0 && blocks.at(i) < rightMax) {
            answer += rightMax - blocks.at(i);
        }
        if (rightMax <= blocks.at(i)) {
            rightMax = blocks.at(i);
        }
    }
    
    cout << answer << "\n";
    
    return 0;
}