빗물
-
[Python] 백준 14719 빗물알고리즘/문제풀이 2021. 8. 7. 18:41
1. 문제 링크 https://www.acmicpc.net/problem/14719 14719번: 빗물 첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500) 두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치 www.acmicpc.net 2. 문제 요약 아래 그림과 같이 빗물의 총량을 구하기 3. 아이디어 정리 투 포인터를 이용하여 빗물 총량을 구한다. ⇒ 오른쪽 포인터 최댓값, 왼쪽 포인터 최댓값을 이용해서 빼준다 오른쪽 포인터 최대값이 큰 경우, 왼쪽 빗물 구하기 & 왼쪽 이동 왼쪽 포인터 최대값이 큰 경우, 오른쪽 빗물 구하기 & 오른쪽 이동 예시를 통한 로직 순서 4. 문제 풀이 4-1. ..