[ICPC 본선 대비 뇌셋] Day 8

백준 8987번 수족관 3 www.acmicpc.net/problem/8987

8987번: 수족관 3

그리디로 찾으면 된다. 제일 물이 많이 빠지는 것을 찾은 후, 그 다음에 물이 제일 많이 빠지는 것을 찾고, 그 과정을 반복한다.

[증명] 제일 많이 빠지는 점을 S1이라고 하자. S1에서 물을 빼면 S1을 기준으로 양 옆으로 갈수록 수위가 높아진다. 그리고 이를 첫번째 수위라고 정의하자.

만약 S2, S3를 뺀 것이 S1, S2를 뺀 것보다 양이 많다고 가정하자.

만약, S2, S3이 첫번째 수위가 다른 곳에 위치해있다면, S3를 S1으로 대체하는것이 무조건 이득임을 쉽게 확인할 수 있다.

만약 S2, S3의 첫번째 수위가 같은 곳에 위치해있다면, 마찬가지로 그림을 잘 그리면 S1의 정의에 의해 S3보다는 S1을 뽑는것이 더 이득임을 증명할 수 있다.

뭔가 증명이 증명같지 않지만, 내일은 양자시험이니까 이정도만 하자ㅋㅋ

S1, ..., Sn일때도 동일하게 논리를 전개할 수 있다. 따라서 그리디.