빗물(백준 14719번)

💡 **Check Point !

( 해당사항 ✓체크 )

1. 막힘 없이 수월하게 풀린 문제인가?✓

2. 1시간이내로 풀렸던 문제인가?

3. 1시간 이상 or 며칠을 두고 풀어봤더니 풀린 문제인가?

4. 시간을 써도 도무지 풀 수 없는 문제인가?

5. 솔루션을 찾아봤는가?

---

난이도 체감

1. 최상

2. 상

3. 중✓

4. 하

---

이해도

1. 완벽히 이해✓

2. 다소 헷갈리는 부분들이 있음

3. 이해 못함

문제

2차원 세계에 블록이 쌓여있다. 비가 오면 블록 사이에 빗물이 고인다.

비는 충분히 많이 온다. 고이는 빗물의 총량은 얼마일까?

나의 풀이

H,W=map(int,input().split())
my_map=list(map(int,input().split()))

answer=0
for h in range(H,0,-1):
    count=0
    l_l=0
    for m in my_map:
        if m>=h:
            if l_l==0:
                l_l+=1
            elif l_l==1:
                answer+=count
            count=0
        else:
            count+=1
print(answer)
                

• my_map에서 나올 수 있는 최대 높이부터 탐색을 시작한다.
• 가로 방향으로 빗물이 담길 수 있는 곳을 찾았다. 쉽게 말하면, 높이가 4인 곳에 빗물이 고이기 위해서는 높이가 4이상인 기둥이 최소 2개가 필요하고, 떨어져 있어야 한다.
• 따라서 l_l에 높이가 h 이상인 기둥이 등장했는지의 정보를 유지하고, 그 다음 기둥이 나올 때까지의 개수를, h높이에서 고인 빗물의 개수(?)라고 코드를 구성한 것이다.

다른 사람들의 풀이

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

ans = 0
for i in range(1, w - 1):
    left_max = max(world[:i])
    right_max = max(world[i+1:])

    compare = min(left_max, right_max)

    if world[i] < compare:
        ans += compare - world[i]

print(ans)

• 양 옆 끝을 제외하고(물이 고일 수 없으므로), 각 열마다 빗물이 얼마나 고이는지 구하는 방식이다.
• i번째를 기준으로 양옆의 최대 값을 구하고, 그 값 중 최소 값을 구한다. (2,4)라면 높이 4까지 고일 수 없기 때문이다.
• 그 후, i칸의 높이를 위에서 구한 compare값에서 빼주면, 그 열에 고여있는 빗물의 양이 된다.
• 이 코드가 더 효율적으로 나온다.