빗물(백준 14719번)
💡 **Check Point !
( 해당사항 ✓체크 )
막힘 없이 수월하게 풀린 문제인가?✓
1시간이내로 풀렸던 문제인가?
1시간 이상 or 며칠을 두고 풀어봤더니 풀린 문제인가?
시간을 써도 도무지 풀 수 없는 문제인가?
솔루션을 찾아봤는가?
난이도 체감
최상
상
중✓
하
이해도
완벽히 이해✓
다소 헷갈리는 부분들이 있음
이해 못함
문제
2차원 세계에 블록이 쌓여있다. 비가 오면 블록 사이에 빗물이 고인다.
비는 충분히 많이 온다. 고이는 빗물의 총량은 얼마일까?
나의 풀이
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
H,W=map(int,input().split())
my_map=list(map(int,input().split()))
answer=0
for h in range(H,0,-1):
count=0
l_l=0
for m in my_map:
if m>=h:
if l_l==0:
l_l+=1
elif l_l==1:
answer+=count
count=0
else:
count+=1
print(answer)
- my_map에서 나올 수 있는 최대 높이부터 탐색을 시작한다.
- 가로 방향으로 빗물이 담길 수 있는 곳을 찾았다. 쉽게 말하면, 높이가 4인 곳에 빗물이 고이기 위해서는 높이가 4이상인 기둥이 최소 2개가 필요하고, 떨어져 있어야 한다.
- 따라서 l_l에 높이가 h 이상인 기둥이 등장했는지의 정보를 유지하고, 그 다음 기둥이 나올 때까지의 개수를, h높이에서 고인 빗물의 개수(?)라고 코드를 구성한 것이다.
다른 사람들의 풀이
1
2
3
4
5
6
7
8
9
10
11
12
13
14
h, w = map(int, input().split())
world = list(map(int, input().split()))
ans = 0
for i in range(1, w - 1):
left_max = max(world[:i])
right_max = max(world[i+1:])
compare = min(left_max, right_max)
if world[i] < compare:
ans += compare - world[i]
print(ans)
- 양 옆 끝을 제외하고(물이 고일 수 없으므로), 각 열마다 빗물이 얼마나 고이는지 구하는 방식이다.
- i번째를 기준으로 양옆의 최대 값을 구하고, 그 값 중 최소 값을 구한다. (2,4)라면 높이 4까지 고일 수 없기 때문이다.
- 그 후, i칸의 높이를 위에서 구한 compare값에서 빼주면, 그 열에 고여있는 빗물의 양이 된다.
- 이 코드가 더 효율적으로 나온다.
This post is licensed under CC BY 4.0 by the author.