[C++] 빗물 (14719번)

빗물

 

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초

256 MB

13522

7523

5914

55.787%

문제

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

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

입력

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

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

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

출력

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

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

---

문제풀이

 

처음 문제를 보고 다음과 같이 접근하였다. 왼쪽 맨 처음을 시작으로 반복문을 돌면서, 그것보다 크거나 같은 값이 있으면 그 사이를 반복문 돌면서 빗물의 값을 더해주는 방식으로 풀었다. 만약 그런 값을 찾지 못했다면, 그나마 가장 큰 기둥 값을 찾아 그 사이를 반복문 돌면서 값을 더해주는 방식으로 풀었다.

예를 들면,

4 8

3 1 2 3 4 1 1 2

라는 값이 있다면, 맨처음 시작 기둥을 3으로 하고 반복문을 돈다. 돌던중 3을 만나게 되면 그 사이인 1 2 를 반복문 돌면서 빗물 값을 정답에 더해준다.

이제 3이 가장 큰 기둥이 되고 그 다음 기둥을 확인하는데 4 이므로 3과 4 사이를 반복문 돌면서 빗물 값을 더해주는데 없으므로 정답에 0이 더해진다.

이제 4이 가장 큰 기둥이 되고 끝까지 반복문을 돈다. 그럼 그나마 큰 기둥이 2이므로 4와 2사이를 반복문 돌며 빗물 값을 더해준다.

풀면서 h값을 사용하지 않는데 왜 주어지는지 의문이 들긴 했지만, 일단 풀었다. 예제는 모두 맞았지만, 다음과 같은 반례에서 실패가 나왔다.

5 6
5 4 1 3 1 2

answer = 3

이렬경우 그나마 큰 값이 4이므로 5와 4사이를 반복하여 돌게 되는데 정답과 다른 값이 나오게 된다.

 

그래서 다시 곰곰히 생각해봤다.

h를 사용해보는 방법을 생각했다.

h부터 1까지 반복을 돌면서 해당 높이보다 크거나 같은 기둥을 찾아 그 사이 수만큼 더해주면 되겠다고 생각했다.

4 8

3 1 2 3 4 1 1 2

4부터 반복문을 돈다. 4는 하나 있기 때문에 아무 값도 더하지 않는다.

이제 3이다. 3보다 크거나 같은 기둥을 반복문 돌며 찾는다. 맨처음 0번을 찾았다. 그 다음 3번을 찾았다. 그럼 그 사이 개수만큼을 정답에 더해준다. 즉 2를 더한다. 3번과 4번도 있지만 이 사이엔 기둥이 없기 때문에 넘어간다.

이제 2다. 2보다 크거나 같은 기둥은 0번 2번 이므로 1을 더해주고, 2번 3번에 0을 더해주고,, 이런식으로 쭉 하면 된다.

 

이제 아까 틀렸던 예시를 보자.

5 6
5 4 1 3 1 2

3에서 돌때 2가 더해지고, 2에서 돌때 1이더해진다. 정답이다.

 

#include <iostream>

using namespace std;

int main() {
    int h, w;
    cin >> h >> w;
    int arr[w];
    for(int i=0; i<w; i++)
        cin >> arr[i];

    int answer = 0;
    for(int i=h; i>0; i--) {
        int start = -1;
        for(int j=0; j<w; j++) {
            if(arr[j] >= i && start == -1) {
                start = j;
            }
            else if(arr[j] >= i) {
                answer = answer + j - (start+1);
                start = j;
            }
        }
    }

    cout << answer;

    return 0;
}