아래 그림 1은 수족관을 앞에서 본 모양이다. 이 수족관에는 물이 가득 차 있다. 만약 수족관 밑바 닥(수평선분)에 구멍을 하나 뚫으면, 구멍을 통해 수족관 안의 물이 빠지게 된다.

그림 1에서 보는 것처럼, X-축은 왼쪽에서 오른 쪽으로 증가하고, Y-축은 위쪽에서 아래쪽으로 증가한다. 바닥을 나타내는 수평선분에 구멍이 있다면, 그 수평선분의 y-좌표와 같거나 작은 위치에 있으면서, 중력에 따라 구멍으로 흘러 들어갈 수 있는 위치에 있는 물은 모두 그 구멍을 통해 외부로 배출된다. 따라서 그림 1의 수족관의 물은 남김없이 모두 빠진다. 수족관에 담긴 물의 양은 물이 차지하는 면적과 일치하는 양이다. 물의 양의 단위는 L(리터)이다. 따라서 그림 1에서 수족관에 물을 가득 채우면 물의 양은 물이 차지하는 면적과 동일한 40L이 다. 그림 2처럼 수족관의 바닥이 복잡할 수도 있다. 수족관 바닥은 수평선분과 수직선분이 번갈아 나타나는 형태이다. 또한 그림 2처럼 수족관 위에서 수직방향으로 수족관 바닥을 보았을 때, 수족관의 바닥이 모두 보이는 (즉, 모든 수평선분이 보이는) 형태이다. 구멍은 항상 수평선분에만 존재하며, 수평선분의 한 가운데에 위치한다. 그리고 하나의 수평선분에 는 최대 하나의 구멍만 존재할 수 있다. 이제 2개의 구멍을 수평선분 2개에 배치해 보자. 이 때, 배출되는 물의 양이 최대가 되도록 배치해야 한다. 만약, 그림 3처럼 2개의 구멍을 배치하면, 원래 물의 양인 26L 중에서 19L만 빠져나가고 7L는 남게 된다.

그러나 그림 4처럼 2개의 구멍을 배치하면, 1L만 남고 25L가 빠져나간다. 결국, 구멍을 2개 배치하는 경우에는 최대 25L의 물을 뺄 수 있는 구멍의 배치가 존재하게 된다.

최대한 많은 양의 물이 배출되도록 K 개의 구멍 을 배치한다고 할 때, 배출되는 최대 물의 양을 출력하는 프로그램을 작성하시오.

수족관(고등)

문제 설명

입력

출력

예제

코드 제출

로그인

LOGIN