[구현/백준] 14719번 : 빗물

- 문제 : https://www.acmicpc.net/problem/14719

 

문제 이해 

- 처음에는 예제만 적용해서 풀이를 작성했는데, 이는 범용적인 케이스를 고려하지 않았기에 틀렸다. 

- 그래서 풀이를 찾아보니 주어진 원소들을 하나씩 탐색하면서 i번째 원소의 왼쪽과 오른쪽 리스트에서 각각 최대값을 구한다. 

- 이 최대값 중 더 작은 값이 i번째 원소 높이가 낮아야 물이 고일 수 있다. 그래서 이 경우에만 높이 차이를 answer에 더해주면 된다. 

 

정답풀이 

h, w = map(int, input().split())
buildings = list(map(int, input().split()))

answer = 0
for i in range(1, w - 1):
    left_max = max(buildings[:i])
    right_max = max(buildings[i + 1:])
    
    compare = min(left_max, right_max)
    
    if buildings[i] < compare:
        answer += compare - buildings[i]
        
print(answer)

 

시도한 풀이 

같은 크기의 최대 높이가 2개 이상일 때 적용이 되지 않는다. 

h, w = map(int, input().split())
buildings = list(map(int, input().split()))

# 최대 높이를 기준으로 왼쪽, 오른쪽 나눠서 진행
# 양쪽 최대 높이 보다 한단계 작은 수가 높이가 되어서 물 채우면 됨
answer = 0
if buildings.count(0) <= w - 2:
    max_value = max(buildings)
    max_index = buildings.index(max_value)
    
    a = max(buildings[:max_index])
    for i in range(max_index):
        answer += a - buildings[i]
        
    if max_index + 1 < w and buildings[max_index + 1]:
        b = max(buildings[max_index + 1:])
        for i in range(max_index + 1, w):
            answer += b - buildings[i]
     
print(answer)

참고 블로그 : https://seongonion.tistory.com/115