https://www.acmicpc.net/problem/24498
문제요약
- n개의 숫자들이 있음(10^6개, 각각은 1 ~ 10^9)
- 하나를 골라서 양쪽을 -1 시키고, 고른 숫자는 +1 시킴(첫번째, 끝은 고를 수 없고, 양쪽 모두 1이상이어야함)
- 최대 높이 구하기
접근법
- 모으면서 높이를 높일 수 있을까 생각해보았음
- a b c 배치에서 일단 b에 모은다고 생각해보면
- 특정 위치를 다 모으게 되면 왼쪽이나 오른쪽이 0이 될 것임. a' b' c'라고 하면
- b'는 정해져 있음 : b' = b + min(a, c), a 또는 c가 0이 될 때까지 작업을 할 수 있으니까
- a' 또는 c'는 0일 것임. a' = 0이고, c' != 0이라고 하자
- b'를 c'쪽으로 모을텐데, c'는 최대 c' + b'만큼 높아질 것임
- 그런데 c'입장에서는 이득 볼 것이 없음 왜냐하면 b에게 준만큼 받은것 + b의 높이이기 때문에 애초에 b쪽으로 모을 필요가 없었음
- 결과적으로 a로는 모을 수가 없을테고, c쪽으로 모아간다고 해도 이득 볼 것은 없음
- 크게 생각해보면 모아가려고 어떤 작업을 하는 것 자체가 이득 볼 것이 없음
- 그냥 기존에 있던 것중에 가장 높은 것
- 양쪽에서 모았을때 가장 높은 것
- 이 중에 큰 값이 큰 값일 것 같다
- 엄밀한 증명인지는 모르겠음
newbieski