[백준][구현] 14719. 빗물

14719. 빗물

 

 

• 내 풀이
  • 가장 높은 블록 기준으로 왼쪽, 오른쪽 나누어서 풀이
  • 기준이 될 블록을 설정하고, 그 기준값 이상의 블록이 나오면 그 사이 빗물을 계산
  • 📍 주의할 점) 가장 높은 블록이 2개 이상인 경우
    • ex) [3, 0, 1, 3, 0, 1, 2, 3]
    • 한번의 빗물 계산이 끝난 뒤 다음 블록 기준을 이전 값과 비교해서 정하지 않으면
    • 3 0 1 3 계산이 끝난 후 그 다음 값인 0을 기준값으로 잡아버릴 수 있기 때문에
    • 3,0 비교해서 큰 값으로 기준을 설정할 수 있게 한다

h,w=map(int,input().split())
lst=list(map(int,input().split()))
max_value=max(lst)
max_idx=lst.index(max_value)

tmp=0
ans=0
for i in range(1,max_idx+1):
    if tmp==-1:
        if lst[i]<lst[i-1]:
            tmp=i-1
        else:
            tmp=i
        continue
    if lst[tmp]<=lst[i]:
        for j in range(tmp, i):
            ans+=lst[tmp]-lst[j]
        tmp=-1
    

tmp=w-1
for i in range(w-2, max_idx-1,-1):
    if tmp==-1:
        if lst[i]<lst[i+1]:
            tmp=i+1
        else:
            tmp=i
        continue
    if lst[tmp]<=lst[i]:
        for j in range(i+1,tmp):
            ans+=lst[tmp]-lst[j]
        tmp=-1

print(ans)

 

 

• 다른 사람 풀이
  • 매 위치에서 해당 위치 양옆으로 가장 큰 값들을 구해
  • 그 중 작은 값으로 빗물 계산

r,c = map(int, input().split())
lst = list(map(int, input().split()))

ans = 0
for i in range(1, c - 1):
    #각 위치에서 양 옆으로 가장 큰 값들 중
    left = max(lst[:i])
    right = max(lst[i+1:])

    #둘 중 작은 값의 높이까지만 빗물이 찬다
    min_value = min(left, right)

    if lst[i] < min_value:
        ans += min_value - lst[i]

print(ans)