빗물 (백준 14719)

문제

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. 해당 위치에서 왼쪽에 있는 블록들 중 가장 길이가 큰 블록(leftMax)과 오른쪽에 있는 블록들 중 가장 길이가 큰 블록(rightMax)을 구한다.

    2-1. 만약 왼쪽 값을 참조할 수 없거나 오른쪽 값을 참조할 수 없는 경우에는 continue

3. leftMax와 rightMax 중 최솟값을 구한다.(min)

4. min에서 현재 위치의 블록 길이를 뺀다.

    4-1. 만약 음수가 나오면 continue

5. 뺀 결과값을 ret에 누적한다.

 

빗물이 고여있기 위해선 현재 위치의 양옆에 자신보다 길이가 긴 블록이 반드시 있어야하며 고여있는 양은 양쪽에서 구한 최대길이값 중 작은 값에서 현재 위치의 블록 길이를 뺀 값이 나온다.

🛠코드

let [a, blocks] = require('fs').readFileSync(0).toString().trim().split('\n');
let [h, w] = a.split(' ').map(Number);
blocks = blocks.split(' ').map(Number);

function solution() {
  let ret = 0;
  for (let i = 0; i < blocks.length; i++) {
    let cur = blocks[i];
    if (i - 1 === -1 || i + 1 === blocks.length) continue;
    let leftMax = Number.MIN_SAFE_INTEGER;
    let rightMax = Number.MIN_SAFE_INTEGER;
    for (let j = i - 1; j >= 0; j--) {
      leftMax = Math.max(leftMax, blocks[j]);
    }
    for (let k = i + 1; k < blocks.length; k++) {
      rightMax = Math.max(rightMax, blocks[k]);
    }
    let min = Math.min(leftMax, rightMax);
    if (min - cur < 0) continue;
    ret += min - cur;
  }

  return ret;
}

console.log(solution());