[백준 14719번] [Kotlin] 빗물

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

14719번: 빗물

 

난이도 : 골드 5
태그 : 구현, 시뮬레이션

 

 

설명

2차원 블록 세계에 비가 왔을 때, 빗물이 고여있는 양을 구하는 문제입니다.

해당 문제의 경우,

각각의 블록을 기준으로 하여

(왼쪽 블럭 중 가장 큰 값, 오른쪽 블록 중 가장 작은 값) 중 가장 작은 값을 구한 뒤,

기준이 되는 블록의 높이만큼 빼주면 해당 블록에 채워지는 물의 양을 구할 수 있습니다.

 

 

빨간색 화살표로 가르키고 있는 블록을 예로 들어보겠습니다.

 

 

왼쪽으로 가장 큰 블록은 연두색 블록, 오른쪽으로 가장 큰 블록은 파랑색 블록으로,

두 블록 중 작은 블록은 연두색 블록입니다.

 

 

 

따라서 두 기둥 중 작은 연두색 기둥의 높이 (3) - 기준 블록의 높이 (2) = 1 만큼 물이 채워집니다.

첫 번째 기둥과 마지막 기둥을 제외한 모든 기둥에 위 작업을 수행하면 됩니다.

 

 

 

소스코드

fun main() = with(System.`in`.bufferedReader()) {
    val (h, w) = readLine().split(" ").map(String::toInt)
    val blockHeights = readLine().split(" ").map(String::toInt).toIntArray()

    var ans = 0

    for (i in 1..<w - 1) {
        var left = 0
        var right = 0

        for (j in 0..<i) {
            left = maxOf(left, blockHeights[j])
        }

        for (j in i + 1..<w) {
            right = maxOf(right, blockHeights[j])
        }

        val height = minOf(left, right)
        ans += maxOf(0, height - blockHeights[i]) // 음수가 나올 수도 있음
    }

    println(ans)
}

 

 

 

 

후기

처음에는 스택인가? 생각했다가, 좀처럼 잘 풀리지가 않아 다른 접근법으로 시도하였습니다.

재밌는 문제였네요.