[Python] 백준 14719 빗물

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

 

문제 분석

• 블록의 크기가 주어졌을 때, 고이는 빗물의 총량은?

 

코드 설계

• 1차
• 현재까지의 최고 높이를 가지고 있고,
• 현재 최고 높이 이상의 블록 : ans += 여태 모인 빗물 and 빗물 0 리셋
• 현재 최고 높이 미만의 블록 : 빗물 += 현재 최고 높이 - 현재 높이
• 이렇게 하니까 현재 높이에 대해 최고 높이만 저장 - 누락 생김 → 빗물이 생기는 오/왼 둘 다 고려해야함
  
  
• 2차
• 물이 고이기 위해서는 자신보다 더 높은 블록으로 왼/오 둘러쌓여야 한다.
• 이때 물이 고이는 양은 왼/오 중 낮은 블록을 기준으로
• m_left = block[0]
• m_right은 m_left 이상의 블록 높이가 나오면 m_right = m_left 갱신
• m_right 다음 블록들에 대해 증가하는 구간 찾기
• 그 사이의 빗물(rain)을 계산하고
• answer += rain
• rain = 0 (reset)

 

정답 코드

1차 - 틀림

import sys
input = sys.stdin.readline

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

highest = block[0]
rain = 0
answer = 0
for i in range(1, len(block)) :
    if block[i] < highest :
        rain += (highest - block[i])
    else :
        highest = block[i]
        answer += rain
        rain = 0

print(answer)

 

다른 정답 코드 : https://seongonion.tistory.com/115, https://velog.io/@rhdmstj17/%EB%B0%B1%EC%A4%80-14719%EB%B2%88-%EB%B9%97%EB%AC%BC-python-%EC%8B%9C%EB%AE%AC%EB%A0%88%EC%9D%B4%EC%85%98-%EA%B3%A8%EB%93%9C-5

import sys
input = sys.stdin.readline

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

ans = 0
for i in range(1, w-1) :
    m_left = max(block[:i])
    m_right = max(block[i+1:])

    compare = min(m_left, m_right)

    if block[i] < compare :
        ans += (compare - block[i])

print(ans)

 

 

2회차 - 25.05.22

• 한 칸씩 주변의 높은 블럭을 계산해서 빗물 양 계산
  
  
• 현재 위치 i에 대해 양쪽 최대 높이를 구하고
• 그 중 작은 높이보다 낮으면 빗물이 고임

import sys
input = sys.stdin.readline

h, w = map(int, input().split())
block = list(map(int, input().split()))
rain = 0

# 맨 앞과 맨 뒤는 빗물이 쌓일 수 없다.
for idx in range(1, w-1) :
    m_left = max(block[:idx])
    m_right = max(block[idx+1:])

    low_block = min(m_left, m_right)

    if block[idx] < low_block :
        rain += low_block-block[idx]

print(rain)