Algorithm/BOJ
[BOJ/Python] 14719_빗물
O773H
2023. 1. 10. 19:47
728x90
문제 출처:https://www.acmicpc.net/problem/14719
14719번: 빗물
첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500) 두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치
www.acmicpc.net
문제
2차원 세계에 블록이 쌓여있다. 비가 오면 블록 사이에 빗물이 고인다.


비는 충분히 많이 온다. 고이는 빗물의 총량은 얼마일까?
입력
첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500)
두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치부터 차례대로 W개 주어진다.
따라서 블록 내부의 빈 공간이 생길 수 없다. 또 2차원 세계의 바닥은 항상 막혀있다고 가정하여도 좋다.
출력
2차원 세계에서는 한 칸의 용량은 1이다. 고이는 빗물의 총량을 출력하여라.
빗물이 전혀 고이지 않을 경우 0을 출력하여라.
예제 입력 1
4 4
3 0 1 4
예제 출력 1
5
예제 입력 2
4 8
3 1 2 3 4 1 1 2
예제 출력 2
5
예제 입력 3
3 5
0 0 0 2 0
예제 출력 3
0
힌트
힌트 1:

힌트 2:

힌트 3:

풀이
우선 코드는 다음과 같다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
|
import sys
h,w = map(int,sys.stdin.readline().split())
h_list = list(map(int,sys.stdin.readline().split()))
higest = h_list.index(max(h_list))
high = h_list[0]
idx = 0
result = 0
sum = 0
for i in range(1,higest+1):
if h_list[i]>=high:
result += high * (i-idx-1) - sum
sum = 0
idx = i
high = h_list[i]
else:
sum+=h_list[i]
high = h_list[-1]
idx = -1
sum = 0
for i in range(2,w-higest+1):
if h_list[-i]>=high:
result += high * (idx+i-1) - sum
sum = 0
idx = -i
high = h_list[-i]
else:
sum+=h_list[-i]
print(result)
|
cs |
제일 높은 높이를 기준으로 좌우를 나누어 탐색하였다.
왼쪽 부분에 고이는 빗물의 총량을 구하는 방법은 다음과 같다.
- 우선 제일 높은 높이의 index를 구하여 higest에 저장한다.
- high에 0번째 index의 높이를 넣고, idx=0으로 초기화한다.
- index 1부터 higest까지 반복문을 이용하여 높이 비교를 한다.
- 만약 high보다 현재 index의 높이가 더 높다면 high만큼의 빗물이 둘 사이 간격만큼(i-idx-1) 고여있음을 의미한다.
- 하지만, 둘 사이에 high보다 낮은 높이의 값들이 있다면, 이를 빼주어야 하므로 sum에 낮은 높이의 블록들의 합을 저장하여 이만큼을 빼준 값이 최종적으로 고여있는 빗물의 양이 된다.
- high에 현재 index의 높이를 저장하고, sum을 초기화하고, idx에 현재 index를 넣는다.
- 이 과정을 higest (제일 높은 높이의 index) 까지 수행한다.
오른쪽 부분에 고이는 빗물의 총량을 구하는 방법도 위와 같다.
Python의 음수 인덱스를 이용하여 -1부터 제일 높은 높이까지 위의 과정을 수행한다.
최종적으로 오른쪽 부분에 고이는 빗물에 총량까지 구하고 나면 이를 출력한다.
728x90