창고 다각형 [백준 실버 2]

누적합 방식으로 해당 문제를 접근하고자 했습니다.

실제 기둥을 순회할때마다, 순회하였던 이전 기둥보다 높이가 낮으면 무시해야했기 때문입니다.

하지만, 이러한 누적합 형태는 가장 높은 기둥이 나올때까지만 반복해야만 합니다. 따라서, 가장 높은 높이의 기둥 위치를 저장한 후, 이를 기준으로 2개의 부분집합으로 나누어 누적합 연산을 각각 수행하였습니다.

let num = Int(readLine()!)!
var arr = Array<(Int,Int)>()

for _ in 0..<num {
    let input = readLine()!.split(separator:" ").map{Int($0)!}
    arr.append((input[0],input[1]))
}

arr.sort(by: {$0.0 < $1.0})

var maxVal:(Int,Int) = (-1,-1)

for i in 0..<num {
    if maxVal.1 < arr[i].1 { maxVal = (i,arr[i].1) }
}

var prefix = Array(repeating: 0, count: num+1)
var ans = arr[0].1

for id in 0..<maxVal.0 {
    prefix[id+1] = max(prefix[id], arr[id].1)
}

for id in stride(from: num-1, through: maxVal.0+1, by: -1) {
    prefix[id] = max(prefix[id+1], arr[id].1)
}

var totalArea = 0

for id in 0..<maxVal.0 {
    let width = arr[id+1].0 - arr[id].0
    let height = prefix[id+1]
    totalArea += width * height
}

// 최고 높이 기둥 오른쪽 영역 계산
for id in maxVal.0..<num-1 {
    let width = arr[id+1].0 - arr[id].0
    let height = prefix[id+1]
    totalArea += width * height
}

print(totalArea+maxVal.1)

 

이 과정에서 가장 시간이 오래 걸렸던 부분은 오른쪽에서 왼쪽으로 수행되는 수행되는 누적합 연산의 인덱스 참조였습니다. 특히 stride의 경우, through와 from에 전달되는 값은 실제로 순회되는 값 중 하나이기에 index out of range를 조심해야합니다. 그에 반해 to는 접근하지 않습니다.