[BOJ] 빗물


  • BOJ의 빗물 문제 풀이입니다

문제 풀이

  • 이 문제는 입력으로 받은 블록에 대해 각각의 블록을 기준으로 왼쪽에서 가장 높은 블록과, 오른족에서 가장 높은 블록 두 블록 중 더 작은 블록과 기준이 되는 블록의 높이를 빼준 값으 모두 더해주는 방법으로 해결할 수 있습니다

  • 예를 들어 [3, 0 ,1 ,4]를 입력으로 받은 경우 3을 기준으로 할 때, 3을 포함해서 왼쪽에서 가장 높은 블록의 높이는 3, 3을 포함해서 오른쪽에서 가장 높은 블록은 4입니다.

  • 따라서 두 블록 중 더 높이가 낮은 블록인 3과 기준으로 잡은 블록 3을 빼면 0이 되고, 높이가 3인 가장 처음 블록에서는 빗물이 고이지 않는 것을 확인할 수 있습니다.

  • 이런 방법으로 모든 블록에 대해 진행하면 빗물의 총량을 구할 수 있습니다


전체 코드

import sys

H, W = map(int, sys.stdin.readline().split())
input_lst = list(map(int, sys.stdin.readline().split()))



result = 0
for i in range(len(input_lst)):
    left_max = max(input_lst[:i+1]) # 나를 포함해서 왼쪽에서 가장 큰 수
    right_max = max(input_lst[i:]) # 나를 포함해서 오른쪽에서 가장 큰 수

    result += (min(left_max, right_max) - input_lst[i])

function solution(H, W, arr) {
  let result = 0;
  for (let i = 0; i < arr.length; i++) {
    let leftMax = arr.slice(0, i + 1).reduce((prev, curr) => {
      return Math.max(prev, curr);
    });

    let rightMax = arr.slice(i).reduce((prev, curr) => {
      return Math.max(prev, curr);
    });

    result += Math.min(leftMax, rightMax) - arr[i];
  }
  return result;
}

Reference









© 2020. by dkmqflx

Powered by dkmqflx