백준 14719 빗물 반례
-
[알고리즘][백준] 14719. 빗물알고리즘 2024. 4. 22. 23:39
문제https://www.acmicpc.net/problem/14719 문제 아이디어 1처음엔 스택 기반의 문제인 줄 알았습니다. 가장 왼쪽부터 탐색하면서, 왼쪽보다 높은 기둥을 만나면 지금까지 스택에 넣었던 걸 하나씩 꺼내면서 높이를 계산해주고, 가장 왼쪽 기준을 다시 업데이트해주면 될 것이라고 생각했습니다.예)3 1 2 3 4 1 1 2 가 있다면,3을 저장해놓고 다음 3을 만날 때까지 스택에 저장해두고,3, [1, 2], 3 에서 1 과 2의 높이에 따라 물의 양을 계산해주면 될 것으로 생각했습니다. 또한 만약 가장 왼쪽 기준 (위에서는 연산을 다 끝낸 후 4부터 시작) 보다 높거나 같은 기둥이 안 나오면 나머지는 다 빼서 나머지 계산을 하면 될 것이라 생각했습니다.예)4 [1 1 2..