https://www.codingame.com/training/easy/retaining-water/discuss
- easy 난이도라 별거 아닌 줄 알았는데 까다로웠음
접근 1
- 상/하/좌/우의 최대값중에서 최소값이 채울 수 있는 최대 높이인줄 알았는데, 물이 흐른다는것을 고려하지 못했음
접근2
- 외벽은 물을 채울 수 없으니 "벽"이라고 두고 완전탐색으로 접근함
- 어떤 위치를 target = 'Z'에서 거꾸로 채워봄
- 인접한 것들이 target보다 작으면 계속 채워봄
- 채워야 하는 곳이 "벽"이면 실패임
- 이렇게 찾다가보면 적절한 target을 찾을 것임
- target으로 채움
- target을 찾을때랑 비슷한데 다른점은
- 채우는 물의 양을 계산해서 합에 더하고
- 처리를 끝냈다는 표시를 함
- "벽"인 경우는 진행하지 않음
- 결과적으로 처리를 끝냈다는 표시 = "벽"과 동일하게 처리함
후기
- 단순한 접근법이 생각나지 않아서 어려웠음
- 백준에 "Water"문제와 비슷했던 것 같았고 그때는 우선순위 큐로 접근했던 것 같은데....아무튼 easy난이도 치고 접근하기 쉽지 않았음
newbieski