14719 빗물
-
백준 14719 빗물Algorithm/BOJ 2021. 5. 2. 14:13
출처: www.acmicpc.net/problem/14719 분류: 구현, 시뮬레이션 접근방식 고이는 빗물의 양을 구하는 문제였습니다. 고이는 빗물은 자신의 양쪽에 자신보다 더 큰 빗물이 있어야 합니다. 저는 처음에 스택으로 접근을 했는데요. 스택에 인덱스와 높이를 넣어주는데, 스택의 탑보다 더 작은 블록을 만나면 추가하고 같으면 새로운 블록으로 갈아치워줍니다. 더 큰 블록을 만나면 탑의 왼쪽과 새로 만난 블록 중 더 작은 높이를 비교하고 스택의 탑에 있는 인덱스와 지금 블록을 비교해서 둘 중 더 작은 높이와 탑의 높이를 빼서, 빗물을 채워주는 방식을 사용했었습니다. 가로 방향으로 칸칸히 채워나가는 방식을 생각했었습니다. 하지만 이렇게 하면, 왼쪽이나 오른쪽 끝이 비어있을 때 문제가 됩니다. 이를 별도로..