https://www.acmicpc.net/problem/14719
14719번: 빗물
첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500) 두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치
www.acmicpc.net
구현 문제다. 특정 알고리즘보단 문제에 어떻게 접근해야 할지 고민해 보게 되는 유형이다.
풀이
입력된 벽의 높이를 좌에서 우로 탐색한다. (탐색값 중 가장 높은 높이 - 현재높이) 값을 임시 변수에 누적. 가장 높은 높이가 갱신되면 여태 구한 임시 변수의 값을 최종 정답에 반영. 새로 바뀐 최대 높이를 기준으로 다시 빗물을 계산한다.
탐색이 끝나고 임시 값을 최종 정답에 반영하지 못했다면, W-1번부터 마지막으로 갱신된 가장 높은 높이의 벽까지 역탐색하며 빗물을 계산하면 된다.
정답 코드
'Problem Solving > BOJ' 카테고리의 다른 글
| [3015] 오아시스 재결합 (0) | 2023.06.12 |
|---|---|
| [14890] 경사로 (0) | 2023.06.03 |
| [5719] 거의 최단 경로 (0) | 2023.04.30 |
| [1711] 직각삼각형 (0) | 2023.04.19 |
| [16169] 수행시간 (0) | 2023.04.11 |