[일반] 백준 11497번 질문점

[익명(59.16)]

https://www.acmicpc.net/problem/11497

오름차순 정렬한다음에

가운데 젤 작은거 놓고

양쪽에 번갈아가며 다음 숫자 넣으면 된다는데

그게 정답이란걸 어떻게 증명해야하지

뭔가 자명한듯하면서 자명하지가 않네...

[익명(61.253)]

정 싫으면, 파라메트릭 돌리면 됨

[익명(14.37)]

이해못했음.. ㅋㅋㅋ

[익명(61.253)]

그리디 증명은, 어차피 가장 작은 애랑 가장 큰 애는 어딘가에 존재해야 하기 때문에, 원 상에서 6시 12시 에 딱 박았다고 생각하면 왼쪽/오른쪽 각각 오름차순으로 놓아야 함. 이 때 번갈아 선택하지 않고 어딘가에 인접하게 선택된 곳이 존재한다면, 번갈아지도록 바꾸는게 이득임. 그림 잘 그려보셈.

[익명(61.253)]

사실 나도 방금 생각한거라 틀릴수있음

[익명(14.37)]

ㄱㅅ

[chromate00(hjroh0315)]

정렬한 후 짝수번째 인덱스만 한번 쭉 돌고 다시 돌아올 때는 홀수번째만 도는 방법을 생각해봅시다. 이렇게 하면 차가 2인 인덱스 간의 높이 차이 중 가장 큰 것이 난이도가 됩니다. (아마 번갈아가며 놓는 방법도 동일할 것입니다) 이때 두 통나무의 위치를 바꿀 경우 어떻게 될지 생각해봅시다.

[익명(14.37)]

생각해보겠습니다

[chromate00(hjroh0315)]

짝수번째 or 홀수번째 내에서만 위치를 바꾸게 되면, 인덱스의 차의 최댓값이 2에서 4로 늘어납니다. 따라서 이 경우는 손해입니다. 짝수->홀수로 전환되는 시점에서 바꿔도 인덱스의 최댓값이 늘어나는데, 차가 2->1->2에서 1->3->1로 바뀐다고 보시면 됩니다. 차의 최댓값이 3으로 늘어났으므로, 손해입니다.