[BOJ] 14719. 빗물

문제

---

골드 5

포인트

---

처음에는 증감의 변화로 마치 극대점을 찾아 물을 채웠지만 반례가 존재했다. 따라서 가장 큰 높이 두 개를 찾아 빗물을 채우는 형식으로 진행했다.

코드

---

h, w = map(int, input().split())
width = list(map(int, input().split()))
height = [0] * h

rightTop = 0
leftTop = 0
total = 0
post = 0
increasing = True

for i in range(w):
    if i == w - 1:
        if width[i] > width[post]:
            rightTop = width[i]
        for j in range(0, min(leftTop, rightTop)):
            total += height[j]
        break

    if increasing:
        if width[post] <= width[i]: # 계속 증가하는 형태일 때
            rightTop = width[i]
            for j in range(rightTop, leftTop):
                total += height[j]
        else: #감소하기 시작하면 그 전이 최고 높이
            rightTop = width[post]
            for j in range(0, min(leftTop, rightTop)): #이 전까지 채운 물
                total += height[j]

            #재시작
            height = [0] * h
            leftTop = rightTop
            for j in range(width[i], leftTop):
                height[j] += 1
            increasing = False
    else: #decreasing
        if width[post] < width[i]: # 증가 시작
            increasing = True
            rightTop = width[i]
        for j in range(width[i], leftTop):
            height[j] += 1
    post = i

print(total)

반례 5 5 5 1 3 1 5

h, w = map(int, input().split())
width = list(map(int, input().split()))

total = 0
maxH, maxIdx = -1, 0
leftTop, leftIdx = width[0], 0

while leftIdx < w - 1:
    for i in range(leftIdx + 1, w):
        if width[i] >= leftTop: #큰게 나타나면 모두 모두 채움.
            for j in range(leftIdx + 1, i):
                total += leftTop - width[j]
            leftTop = width[i]
            leftIdx = i
            maxH = -1
            maxIdx = i
            break

        if maxH < width[i]: #leftTop 보다 작지만 가장 큰 것을 찾음
            maxH = width[i]
            maxIdx = i

        if i == w-1:
            for j in range(leftIdx + 1, maxIdx):
                total += (maxH - width[j])
            leftIdx = maxIdx
            leftTop = maxH
            maxH = -1
print(total)