백준 14719] C++ 빗물

해당 문제는 백준 사이트에서 풀 수 있습니다.

 

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

 

1. 문제

 

 

문제

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:

힌트 2:

힌트 3:

출처

University > 충남대학교 > 생각하는 프로그래밍 대회 D번

• 문제를 만든 사람: isku

 

 

 

 

 

2. 조건

1.  위 그림과 같은 블록이 있을 때 그 사이에 들어갈 수 있는 빗물의 양을 구하여라.

2. 담을 수 없는 공간이 있다면 0으로 처리한다. ( 0, 1, 4, 0 )이라고 할 때

 

3. 풀이

해당 문제는 내 자신을 기준으로 왼쪽 오른쪽을 검색한 다음 왼쪽기준 가장 큰놈과 오른쪽 기준 가장 큰놈 중

제일 작은놈을 기준으로 나 자신을 빼면 해당 위치에서 받을 수 있는 물의 양이 나오게 됩니다.

 

즉,

1.

 

 

 

2.

 

3.

 

 

이 과정을 반복하면 됩니다. 이렇게 되면 쉽고 간단하게 빗물의 양을 구할 수 있게 됩니다.

 

4. 코드

#include <iostream>
#include <vector>

int main() {
    int T;
    int N, M, K;
    int X, Y;
    int answer = 0;

    cin >> N >> M;
    vector<int> v(M);

    for (int i = 0; i < M; i++)
        cin >> v[i];

    for (int i = 1; i < M - 1; i++) {
        int left = 0; int right = 0;
        //왼쪽 최대 값
        for (int j = 0; j < i; j++) left = max(left, v[j]);
        //오른쪽 최대 값
        for (int j = M - 1; j > i; j--) right = max(right, v[j]);
        //빗물 계산
        answer += max(0, min(left, right) - v[i]);
    }

    cout << answer << endl;
    return 0;
}