14719. [Python]빗물

1. 문제

 

https://www.acmicpc.net/problem/14719

 

2. 접근 방법

 

• 시간 제한: 1초
• 메모리 제한: 256MB
• 구현

 

3. 파이썬 코드

 

# H, W 인풋 처리
H, W = map(int,input().split())
# 빗물의 양 리스트로 저장
rains = list(map(int,input().split()))
# 몇칸이 쌓이는지 저장할 변수
answer = 0
# 1 ~ W-2 까지 반복
for i in range(1,W-1):
    # i 값을 기준으로 왼쪽에서 제일 큰 값 찾기
    left_value = max(rains[:i])
    # i 값을 기준으로 오른쪽에서 제일 큰 값 찾기
    right_value = max(rains[i:])
    # 두 값중 작은 값 찾기
    min_value = min(left_value,right_value)
    # 현재 빗물의 양이 최소 값보다 작은 경우
    if rains[i] < min_value:
        # 빗물 저장 할 변수에 min_value 에서 현재 빗물 값 감소
        answer += min_value - rains[i]
# 정답 출력
print(answer)

 

4. 문제를 풀고난 후 생각

 

• 빗물이 리스의 반복문을 순회하며 값을 제외하는 식으로 접근을 했다가 예외적인 상황을 고려하여 다시 고민을 진행함
  • 예외 => 3 2 2 1 1 2 2 의 경우 기존에 코드를 작성한 방법으로 접근시 3보다 큰 값이 없기 때문에 빗물의 카운트가 0이 되는 예외가 발생
• 새로 접근한 방식은 각 위치에서 왼쪽에서 큰값을 찾고 오른쪽에서 큰 값을 찾아서 두 값중 더 작은 값만큼 현재 위치에서 빗물을 빼서 정답 변수에 더해주는 식으로 접근했다.
• 현재 위치의 빗물이 최소 값보다 작은 경우만 연산을 처리해줬기 때문에 3 2 3 2 3 이런 경우에 빗물을 더해주지 않을 수 있는 예외처리를 진행함
• 문제를 접근하는 방식에 있어서 고민을 많이함

 

5. 문제를 푸는데 도움이 되는 지식

 

• 구현