[백준, C++] 14719 - 빗물

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

14719번: 빗물

 

문제 분석

문제를 보자마자 최근 풀었던 한 문제가 생각났다. 아래에 그 문제를 풀고 작성한 포스트 링크를 첨부하겠다.

https://optimal-solution.tistory.com/entry/%EB%B0%B1%EC%A4%80-C-2304-%EC%B0%BD%EA%B3%A0-%EB%8B%A4%EA%B0%81%ED%98%95

[백준, C++] 2304 - 창고 다각형

14719번 빗물 문제는 2304번 창고 다각형 문제와 매우 유사하다(첨부된 이미지까지도 유사하다). 그래서 창고 다각형 문제를 풀 때와 동일한 방법으로 풀 수 있을 것이라 생각했다.

 

가장 높은 블록을 기준으로 왼쪽과 오른쪽을 구분하고, 왼쪽에 고이는 빗물의 양과 오른쪽에 고이는 빗물의 양을 더하는 것이다.

 

코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int h, w;
int heights[500];
int result;

void getInput();
void solve();
void printResult();

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

    getInput();
    solve();
    printResult();

    return 0;
}

void getInput() {
    cin >> h >> w;
    for (int i = 0; i < w; i++) {
        cin >> heights[i];
    }
}

void solve() {
    int highestValue = 0;
    int index = -1;
    for (int i = 0; i < w; i++) {
        if (highestValue < heights[i]) {
            highestValue = heights[i];
            index = i;
        }
    }

    highestValue = heights[0];
    for (int i = 1; i < index; i++) {
        if (highestValue > heights[i]) {
            result += highestValue - heights[i];
        } else if (highestValue < heights[i]) {
            highestValue = heights[i];
        }
    }

    highestValue = heights[w - 1];
    for (int i = w - 2; i > index; i--) {
        if (highestValue > heights[i]) {
            result += highestValue - heights[i];
        } else if (highestValue < heights[i]) {
            highestValue = heights[i];
        }
    }
}

void printResult() {
    cout << result << "\n";
}

 

코드 설명

입력과 출력을 제외하고, solve() 부분만 설명하겠다. 사실 편의상 입력부(getInput()) / 풀이부(solve()) / 출력부(printResult())를 나누는 것인데(그러니까 문제 풀이 자체에만 집중하기 위해서 나누었다), 가장 높은 블록의 인덱스를 구하는 건 입력부에서 처리해도 되긴 하다. 하지만 풀이를 입출력과 분리하고 싶어 나는 나눴으니 그렇게 이해하고 설명을 보면 좋을 것 같다.

 

먼저 가장 높은 블록의 인덱스를 구한다. 그리고 이 인덱스를 index라는 변수에 할당한다.

 

다음으로 가장 높은 블록의 왼쪽에서 고인 빗물의 총량을 계산한다. 지금까지 가장 높은 블록의 높이(highestValue)를 heights[0]으로 지정하고, 인덱스 [1, index)를 순회한다. 그러면서 heights[i]가 highestValue보다 큰지, 작은지를 나눠 분기 처리한다. heights[i]가 highestValue보다 크다면, 즉 이전까지 나왔던 블록보다 더 높은 블록이 등장한 셈이므로 최고값을 갱신해준다. heights[i]가 highestValue보다 작다면, 여기는 highestValue까지 물이 고일 수 있다(그 원리는 index 위치에 가장 높은 블록이 있고, 따라서 물은 최대 highestValue까지 고일 수 있다는 뜻이기 때문임). 그래서 result에 (highestValue - heights[i])를 더해주게 된다. 이를 [1, index)까지 순회하면서 반복한다.

 

그리고 마지막으로, 가장 높은 블록의 오른쪽에서 고인 빗물의 총량을 계산한다. 지금까지 가장 높은 블록의 높이(highestValue)를 heights[w - 1]로 지정하고, 인덱스 (index, w - 1]을 역방향으로 순회한다. 그러면서 앞에서 했던 것처럼 heights[i]와 highestValue를 비교하며 빗물이 고인 양을 result에 추가하거나, highestValue 값을 갱신해준다.

 

최종적으로 우리는 가장 높은 블록의 왼쪽 / 오른쪽에 고인 빗물의 총량을 계산할 수 있게 된다.

 

(근데 왜 빗물 문제는 골드 문제고 창고 다각형 문제는 실버 문제일까 ? 풀이는 같은데 말이지)