문제풀이/한국정보올림피아드 (1) 썸네일형 리스트형 백준 8987 수족관 3 (KOI 2013 4번) 문제 설명(링크) https://www.acmicpc.net/problem/8987 8987번: 수족관 3 입력의 첫 줄은 수족관의 경계에 있는 꼭짓점의 개수 N(4 ≤ N ≤ 300,000)이 주어진다. N은 짝수이다. 수족관의 경계는 항상 꼭짓점 (0, 0)부터 시작한다. 그리고 마지막 꼭짓점은 (A, 0)의 형태로 끝난 www.acmicpc.net 풀이 풀이가 다양한 것 같은데, 내가 푼 풀이 기준으로 설명하겠다. 우선 수족관의 모양이 히스토그램과 유사하므로, 카르테시안 트리로 모델링할 수 있다. 수족관을 카르테시안 트리로 모델링하면 특정 정점을 선택하면 그 정점과 그 정점의 모든 조상 정점에 해당하는 영역의 물이 빠진다. 또한 한번 물이 빠진 영역은 당연하게도 물을 다시 뺄 수 없다. 이런 특성들.. 이전 1 다음