#14719 빗물

문제

---

 

코드

---

fun main() = with(System.`in`.bufferedReader()) {
    val (h, w) = readLine().split(' ').map { it.toInt() }
    val block = readLine().split(' ').map { it.toInt() }
    val world = Array(h) { IntArray(w) }
    var result = 0
    for (i in block.indices) {
        for (j in 0..<block[i]) {
            world[j][i] = 1
        }
    }
    for (i in 0..<h) {
        // 한 행(h)에서 w 인덱스의 min, max 값 찾고, 그 안에 있는 world[i][j] == 0 인 값 갯수 세기
        var temp = 0
        var min = w - 1
        var max = 0
        for (j in 0..<w) {
            if (world[i][j] == 1) {
                if (j < min) min = j
                if (j > max) max = j
            }
        }
        for (j in min + 1..<max) {
            if (world[i][j] == 0) temp++
        }
        result += temp
    }
    println(result)
}

 

풀이

---

처음에는 어떻게 풀어야 하나 좀 막막했는데, 한 행씩 보면 쉽게 풀린다.

이 부분에서 아래에서 두 번째 행을 보자.

블록이 차 있는 인덱스의 최소값과 최대값을 저장해두면, 그 사이에 블록이 없는 공간엔 무조건 빗물이 차 있게 된다.

2번째 행의 경우

세 번째 행의 경우

따라서 min, max index 값을 찾고, 그 안에 비어있는 공간의 개수를 세면 됨

 

h와 w의 범위가 500까지밖에 되지 않아 이중 for문이 들어가도 시간 제한 없이 동작하는 것 같다.