구현 문제는 풀 때마다 느끼는 거지만 문제 해결 방향이 가장 중요한 것 같다.. 보통 문제에서 답을 찾는 과정을 설명해주면서 그 방향을 귀띔해주는 경우가 많은데 이 문제는 없어서 더 헤맸던 것 같다ㅎㅎ
이 문제를 보고 내가 생각했던 문제 풀이의 방향은 물을 담는 블록이 되는 높이를 하나로 묶어 그 안에 있는 물을 계산하는 방법이었다. 그냥... 빗물의 모양보고 양동이로 담는 것 같아서 생각했던 풀이였다. 양동이를 height으로 두고 알고리즘으로 구현한 코드는 다음과 같았다.
import sys
input = sys.stdin.readline
h, w = map(int, input().split())
blocks = list(map(int, input().split()))
cnt = 0
black_block = 0
rainwater = 0
height = [blocks[0]]
def put_rainwater():
global black_block, cnt
if len(height) == 2:
height.pop(0)
height.append(blocks[i])
min_value = min(height)
rain_drop = cnt * min_value - black_block
cnt, black_block = 0, 0
return rain_drop
for i in range(1, w):
if i == w-1:
rainwater += put_rainwater()
elif blocks[i] >= height[-1] or height[-1] >= blocks[i] > blocks[w-1]:
rainwater += put_rainwater()
else:
cnt += 1
black_block += blocks[i]
print(rainwater)이 풀이는 말도 안되는 생각이었는데,, 일단 양동이처럼 담으려면 for 문을 돌릴 때 다음에 나올 크기 중 어떤 높이를 양동이의 height로 해야하는지 기준이 명확하지 않았다. 가장 큰 높이가 height인 것이 확실하지 않았기 때문이다. 그래서 다음과 같은 반례에 모두 통과될 수가 없다.
4 9
3 1 2 3 1 4 1 0 1
4 9
3 1 2 3 1 4 1 1 1그래서 이 알고리즘은 미련없이 버리도록 한다🐸
두번째 생각한 방법은 어떤 블록에 대해 왼쪽의 최고 높이와 오른쪽의 최고 높이를 비교해 낮은 높이만큼 물을 채우는 것이다.
이렇게 하면 for문을 돌리면서 앞, 뒤 리스트의 최고값만을 얻으면 되므로 알고리즘을 올바르게 작성할수 있당
import sys
input = sys.stdin.readline
h, w = map(int, input().split())
blocks = list(map(int, input().split()))
ans = 0
for i in range(1, w-1):
height = min(max(blocks[:i]), max(blocks[i+1:]))
if height - blocks[i] > 0:
ans += (height - blocks[i])
print(ans)통과~
