[boj] 14719 빗물

문제

[boj] 14719 빗물

---

풀이

실패한 시도)
빗물이 고이려면 구덩이가 있어야 하고, 구덩이의 양 옆 벽 중 낮은 쪽의 높이에 맞춰 채워진다.
왼쪽부터 차례로 봤을 때, i번째보다 i+1번째가 작으면 i번째가 벽이다!
벽을 먼저 구한 후 빗물을 채운다

이 경우 배열이 4 0 0 2 0 4처럼 가운데 기둥이 잠기는 경우의 빗물 양이 제대로 계산되지 않음

그래서 미리 벽을 다 구하고 물을 채우는 게 아니라, 인덱스를 이동하면서 자신의 자리 기준 왼쪽에서의 최댓값, 오른쪽에서의 최댓값을 구해 벽으로 설정하고 자신의 자리에서 빗물을 채우는 방식으로 고쳐 구했다

---

코드

javascript

// boj 14719 빗물
// implementation
const input = require("fs").readFileSync("/dev/stdin").toString().split("\n");

const h = input[0].split(" ").map(Number)[0];
const w = input[0].split(" ").map(Number)[1];
const arr = input[1].split(" ").map(Number);

let rain = 0;
for (let i = 1; i < w - 1; i++) {
  let left = 0,
    right = 0;

  for (let j = 0; j < i; j++) {
    if (arr[i] < arr[j]) left = Math.max(left, arr[j]); //왼쪽 벽
  }

  for (let j = i + 1; j < w; j++) {
    if (arr[i] < arr[j]) right = Math.max(right, arr[j]);
  }

  if ((left !== 0) & (right !== 0)) rain += Math.min(left, right) - arr[i];
}
console.log(rain);