기로에 서다

문제 www.acmicpc.net/problem/14719 14719번: 빗물 첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500) 두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치 www.acmicpc.net 풀이 1. 어떤 칸에 빗물이 채워지는 조건에 대해서 생각해볼 때, 그 칸을 제외한 (좌측의 최대 높이, 우측의 최대 높이) 둘 중 작은 높이에서 어떤 칸의 높이를 뺀 만큼 채워진다는 걸 알 수 있습니다. (물론 물이 채워져야 하므로 좌측의 최대 높이, 우측의 최대 높이는 어떤 칸의 높이보다 높아야 합니다.) 2. i칸을 제외한 i칸 좌측의 최대 높이를 $pre[i]$, 우측의 최대높이를 ..