[Python] 백준 14719 - 빗물

https://www.acmicpc.net/problem/14719

14719번: 빗물

 

내 코드

h,w = input().split()
h,w = int(h),int(w)

x = input().split()
x = [h - int(i) for i in x]
arr = [[0 for i in range(w)]for j in range(h)]

for i in range(h):
    for j in range(w):
        if x[j] <= i:
            arr[i][j] = 1

cnt=0
for i in range(h-1,-1,-1):
    while True:
        if 0 not in arr[i]:
            i-=1
        else:
            break
    if arr[i].count(1) >=2:
        for j in range(arr[i].index(1)+1,len(arr[i]) - 1 - list(reversed(arr[i])).index(1)):
            if arr[i][j] == 0:
                cnt+=1
                arr[i][j] =1
print(cnt)

문제에 나온 그림과 같이 이차원 리스트를 만들어주었다.(블록 1, 비어있으면 0 , 후에 빗물이 찰 경우 1로 변경)

한 줄 모두 빗물이 고여있거나 블록으로 이루어져있으면 없애주는 방식으로 풀었다.

빗물을 채우는 방법은 블록이 2이상일때 (블록이 하나일 경우는 빗물이 찰 수 없음) 리스트의 가장 앞에 있는 블록(1)의 위치부터 리스트를 가장 뒤에 있는 블록의 위치(리스트를 reversed 한 후 가장 앞에 있는 1의 위치를 구하였다) 를 구하여 0일때만 빗물을 채워주었다.

 

---

다른사람 코드

h,w=map(int,input().split())
m=list(map(int,input().split()))
s=0
for i,d in enumerate(m):
    s+=min(max(m[:i+1]),max(m[i:]))-d
print(s)

리스트를 돌면서 현재 위치하고있는 곳의 왼쪽에 위치한 벽들과 오른쪽에 위치한 벽들을 비교하면서 풀었다.

자신보다 앞에 있는 벽들 중에서 가장 큰 벽을 구하고, 자신보다 뒤에 있는 벽들중에서 가장 큰 벽을 구한다.

구해놓은 두 벽에서 더 작은 벽을 기준으로 빗물이 고이므로 최솟값을 구하고 자신의 위치에서 고일 수 있는 빗물 양을 구하기위해 -d를 해준다.