(python) 백준 #14719 - [G5] 빗물

14719번: 빗물

 

다양한 풀이 방법 (행단위, 열단위, 스택)

매우 다양한 풀이로 해결할 수 있는 문제인 것 같습니다. 전 두가지 방법을 시도해봤고 접근법은 코드에 주석으로 달아놨습니다.

1. 행단위로 해결하기

2. 열단위로 해결하기

2번이 가장 많이 알려진 풀이인 것 같습니다.

2번의 경우 max(slicing)으로 해결할 수 있고 그게 코드상 훨씬 간결하긴한데 모든 칸에 대해서 왼쪽, 오른쪽의 max 값을 구하면 O(N*N)이라 O(N)으로 해결해보려고 메모이제이션을 시도해봤습니다.

 

이 외에도 스택으로 해결할수도 있습니다.

스택으로 깔끔하게 해결한 코드는 전 조금 찾아봤을때 이것밖에 못봤는데요..!

이분 코드를 참고했습니다.

https://www.acmicpc.net/source/52609455

_, _ = map(int, input().split())
walls = list(map(int, input().split()))

stack = []
answer = 0

for i, h in enumerate(walls):
    while stack and walls[stack[-1]] < h:
        b = walls[stack.pop()]
        if not stack:
            break
        d = i - stack[-1] - 1
        wh = min(walls[stack[-1]], h) - b
        answer += d * wh
    stack.append(i)

print(answer)

이해를 위해서 그린 그림입니다.

 

 

코드

'''
Title   : 빗물
Link    : https://www.acmicpc.net/problem/14719
Level   : G5
Problem : 고인 빗물의 총량을 구한다.
DATE    : 23.07.30
'''

import sys

# 행단위로 해결
# 빗물과 기둥넓이를 모두 구한 후 기둥넓이를 빼줍니다.
# 한 행의 가장 왼쪽 기둥과 가장 오른쪽 기둥을 찾으면 그 사이는 무조건 물이나 기둥이 들어있다는걸 이용합니다.
def solution1(input) : 
    H,W = map(int, input().split())
    L = list(map(int,input().split()))
    water = 0
    for h in range(H,0,-1) :
        minw, maxw = -1, -1
        for w, wh in enumerate(L) :
            if wh >= h :
                if minw == -1 : minw = w
                else : maxw = w
        if minw == -1 : continue
        elif maxw == -1 : water+=1
        else :
            water+=(maxw-minw+1)
    water-=sum(L)
    print(water)
    

# 열단위로 해결
# 한 열의 왼쪽의 가장 높은 기둥과 오른쪽의 가장 높은 기둥 중에서 낮은 기둥이 물의 높이가 됩니다.
# (물높이-기둥 높이) 가 0보다 크면 그만큼 물이 찰 수 있습니다.
def solution2(input) : 
    H,W = map(int, input().split())
    L = list(map(int,input().split()))
    LR = list(reversed(L))
    leftmax = [0] # 보다 왼쪽의 가장 높은 기둥 높이
    rightmax = [0] # 보다 오른쪽의 가장 높은 기둥 높이
    lm = 0
    rm = 0
    for w in range(W-1) :
        lm = max(lm, L[w])
        rm = max(rm, LR[w])
        leftmax.append(lm)
        rightmax.append(rm)
    rightmax = list(reversed(rightmax))
    water=0
    for i in range(W) :
        water+=max((min(leftmax[i],rightmax[i])-L[i]),0)
    print(water)

 

my solved.ac :

solved.ac