[C++]백준 14719번: 빗물

문제

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

14719번: 빗물

 

문제이해

 

• 첫 번째 줄에 H(세로의 길이)와 W(가로의 길이)를 입력한다.
• 두 번째 줄에 W개의 블록이 쌓인 높이를 입력한다.
• 고이게 되는 빗물의 총량을 출력한다.

 

가로를 기준으로 N번째의 위치에 고이게 되는 빗물의 높이를 구하기 위해서는 N번째 위치를 기준으로 왼쪽과 오른쪽에 가장 높게 쌓인 부분을 구해야 합니다.

 

이후 왼쪽의 가장 높게 쌓인 부분과 오른쪽의 가장 높게 쌓인 부분 중 더 높이가 작은 부분과 N번째 위치의 높이의 차를 구해주면 그게 바로 N번째 위치에 쌓이게 되는 빗물의 높이게 되게 됩니다.

 

문제에 주어진 예시를 통해 설명해보도록 하겠습니다.

화살표로 표시해 둔 부분에 쌓이게 되는 빗물의 양을 위의 설명을 토대로 확인해 보도록 하겠습니다.

화살표로 표시해 둔 부분(A)의 높이는 1입니다.

 

• A의 왼쪽 부분에서 가장 높이가 큰 부분(B)의 높이는 3입니다.

 

• A의 오른쪽 부분에서 가장 높이가 큰부분(C)의 높이는 4입니다.

 

• B와 C중 높이가 작은 부분은 B이며 그 높이는 3입니다.

 

• B의 높이 - A의 높이 = 3 - 1 = 2

 

따라서 A부분에 쌓이게 되는 빗물의 높이는 2가 됩니다.

 

 

해당 과정을 N개의 모든 위치에 대해서 전부 실행시키게 된다면 전체에 쌓이게 되는 빗물의 총량을 구할 수 있게 됩니다.

 

해당 내용을 코드로 작성한 내용입니다.

문제풀이

#include <iostream>
#include <vector>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int T;
    int N, M, K;
    int X, Y;
    int sum{ 0 };
    cin >> N >> M;
    vector<int> walls(M);

    for (int i = 0; i < M; i++)
        cin >> walls[i];
    for (int i = 1; i < M - 1; i++) {
        int L, R;
        for (int a = 0; a < i; a++)
            L = max(L, walls[a]);
        for (int a = M - 1; a > i; a--)
            R = max(R, walls[a]);
        sum += max(0, min(L, R) - walls[i]);
    }
    cout << sum;
}

위에서 설명한 대로 특정 지점을 기준으로 왼쪽에서 가장 높은 부분과 오른쪽에서 가장 높은 부분을 찾아 비교한 후 작은 부분과 원래 지점의 높이의 차를 빼서 그 부분에 쌓이게 될 빗물의 총량을 구했습니다.

 

 

문제후기

어렵지 않은 문제였습니다.