백준 14719
고이는 빗물의 총량 구하기.
- 2차원 세계에 블록이 쌓여있다. 비가 오면 블록 사이에 빗물이 고인다.
- 첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500)
- 두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치부터 차례대로 W개 주어진다.
- 따라서 블록 내부의 빈 공간이 생길 수 없다. 또 2차원 세계의 바닥은 항상 막혀있다고 가정하여도 좋다.
- 2차원 세계에서는 한 칸의 용량은 1이다. 고이는 빗물의 총량을 출력하여라.
- 빗물이 전혀 고이지 않을 경우 0을 출력하여라.
입출력
| 입력 | 출력 |
|---|---|
| 4 4 3 0 1 4 | 5 |
| 4 8 3 1 2 3 4 1 1 2 | 5 |
| 3 5 0 0 0 2 0 | 0 |
접근 방식
: 완전 탐색인가? 그냥 숫자 빼기로 할 수 있을 것 같은데..
알게된 점
해당 원소 기준으로 왼쪽에서 가장 큰 값, 오른쪽에서 가장 큰 값을 구해서 둘 중 더 작은 값을 기준으로 해당 원소의 차이를 구한다. -> 이 차이 값들의 합
코드
h, w = map(int, input().split())
block = list(map(int, input().split()))
ans = 0
for i in range(len(block)):
lmax = max(block[:i+1])
rmax = max(block[i:])
pivot = min(lmax, rmax)
ans += (pivot - block[i])
print(ans)
알면 아주 쉬운 문제인 것 같다.
