백준 8985 수족관 2 8985번: 수족관 2 입력의 첫 줄은 수족관의 경계를 구성하는 꼭짓점의 개수 N (4 ≤ N ≤ 300,000)이 주어진다. N은 짝수이다. 수족관의 경계는 항상 꼭짓점 (0, 0)부터 시작한다. 그리고 마지막 꼭짓점은 (A, 0)의 형태로 www.acmicpc.net 문제를 만나고 나서 생각을 시작해 보면 금방 발견할 수 있는 것이 있다. 계산을 할 구간의 최소 높이가 존재하는 곳을 기준으로 부분 부분 나뉘어 각각의 연산을 다시 실행한다는 것 이러한 특징을 찾으면 바로 분할 정복임을 눈치챌 수 있을 것이다. 그러면 문뜩 머릿속에 그럼 물이 빠져나가는 시간은 어떻게 구하지? 가 떠오른다 분할된 구간에서 물은 얼만큼 빠져나가고 시간은 얼만큼 걸리는가. 분할됐을 때의 높이에서 분할..
