[Python] 백준 14719 빗물

🧑‍💻 [Python] 백준 14719 빗물

Gold 4 - 구현

입력 값

M, N = 4, 8

3 1 2 3 4 1 1 2

 

i	left	right	min(max(left), max(right))	block[i]	water
1	3	2, 3, 4, 1, 1, 2	3	1	2
2	3, 1	3, 4, 1, 1, 2	3	2	3
3	3, 1, 2	4, 1, 1, 2	3	3	3
4	3, 1, 2, 3	1, 1, 2	3	4	3
5	3, 1, 2, 3, 4	1, 2	2	1	4
6	3, 1, 2, 3, 4, 1	2	2	1	5

• left, right 는 현재의 인덱스 기준으로 왼쪽과 오른쪽에, 더 큰 지역이 있는지 보는 것이다
  • 이것을 통해서 물이 고이는지 안 고이는지 알 수 있다
• min(max(left), max(right)) 이 block[i]보다 클 때에 water 에 고인 물의 값을 더해준다
  • min(max(left), max(right)) - block[i]

코드

N, M = map(int, input().split())
block = list(map(int, input().split()))


water = 0
for i in range(1, M - 1):
    # 해당 자리 양 옆으로, 물이 고일 수 있도록 벽돌이 있는지 확인 하는 것
    left, right = block[:i], block[i + 1:]
    wall = min(max(left), max(right))

    # 고인 물 계산하기
    if wall > block[i]:
        water += wall - block[i]

print(water)