백준 온라인 저지 6549
빗물 채우기 문제로 모 회사 면접에 나왔다
당시 분명 풀어본건데 긴장한 탓인지 못풀어서 몹시 원통했던 기억에 있다. 출근하다가 급 생각나서 기록해보겠다
다양한 풀이방식이 있겠지만 내가 아는 방식은 2가지이다.
1. 스택 활용
O(n)
단순히 값을 넣어가며 앞뒤로 2번 Sweep해서 구하는 방식
2. 세그먼트 트리 + 분할 정복
O(nlogn)
세그먼트 트리로 구간 내 최대값을 구하고 분할정복으로 반복하는 방식
추후 정리