NHN_백준_14719 (빗물_Brute Force 반반)

• 링크 : https://www.acmicpc.net/problem/14719

---

문제 접근하면서 생각한 것 메모 (걍 습관 들이기 용)

• 일단 창고다각형(백준 2304)랑 같은 문제다

• 반반 브루트폴스인건 똑같을 듯

• U나 UU 인 경우까지 테스트케이스로 나왔는데, UUU ~ UUUUUU 이런 경우는 없겠지..?

• 1 이상일 경우에만 물을 채우자(?)

처음에 생각했던 수도코드 (걍 메모용임 정답이랑 좀 다르다)

* answer = 0

한쪽만 봤을 때
* while(끝 idx까지 이동):
  - water = 0      ~> 여기서 초기화
  - while():        ~> 1회 진행 ~> 이러면 uuuuuu이런 경우도 가능!
  - 이때 물을 채우는 양은
  - 일단 plus = 현재 높이 저장해두고
  - if h > nh :
  -     water += (plus - 다음) = (h - nh) ~> 이때 다음(nh)는 계속 다음 idx꺼로 바뀌어감
  - elif h <= nh:
  -      answer += water
  -      break

---

정답 코드

• 앞서 풀었던 백준 2304 (창고 다각형)과 똑같이 접근하면 되는 문제
  • 특이한게 테스트케이스 중 3번째꺼 왜 따로 처리할 필요 없었는지 고민하려던 찰나에 정답 되어버림
• 어쨌든 핵심은 "max높이"를 기준으로 반반 수행!!!
• 그리고 prev 높이가 같아져도 다음 높이로 바꿔줘야함!! 이동해야 하기 때문

''' 내가 짠 - only 내힘 '''
answer = 0

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

max_t_idx = graph.index(max(graph))

# 왼쪽부터 max높이까지
prev = graph[0]
for i in range(1, max_t_idx):
    if prev <= graph[i]:              # 같아져도 바꿔줘야!(이동해야!) + 테케 3번도 이래서 ㅇㅋ임(물 안넣음)
        prev = graph[i]               # prev 변경 후 그간 쌓은 물 추가해준다
    elif prev > graph[i]:
        answer += prev - graph[i]     # prev 높이 유지
    
# 오른쪽부터 max높이까지
prev = graph[-1]
for i in range(w-2, max_t_idx, -1):
    if prev <= graph[i]:              # 같아져도 바꿔줘야!(이동해야!) + 테케 3번도 이래서 ㅇㅋ임(물 안넣음)
        prev = graph[i]               # prev 변경 후 그간 쌓은 물 추가해준다
    elif prev > graph[i]:
        answer += prev - graph[i]     # prev 높이 유지

print(answer)