출처: 백준 온라인 저지
https://www.acmicpc.net/problem/11497
못 푼 이유
문제 풀이를 위한 기본 아이디어 자체를 생각해내지 못해서 못 푼 문제다.
다른 사람들의 풀이
다른 사람들의 기본 아이디어는 조금씩 다르긴 하지만 다음과 같다. 통나무를 높이 순서대로 정렬한다. 그 다음 가장 작은 통나무부터 순서대로 양 끝에서부터 배치한다. 그러면 결과적으로 높이 순서로 정렬했을 때, 2칸 이내에 있는 통나무들끼리만 인접하게 할 수 있다.
예를 들어, 통나무 10개의 높이가 각각 1, 3, 5, 7, 9, 12, 14, 16, 18, 20이라고 하면 아래와 같이 배치한다.
| 1 | 5 | 9 | 14 | 18 | 20 | 16 | 12 | 7 | 3 |
|---|
이 해답에 대해 이러한 의문이 들었다. 높이 정렬에서는 바로 인접하지만 유독 그 차이가 큰 경우에는 바로 인접하게 해야 하는 것 아닌가? 이를 테면, 통나무 간격이 1, 2, 3, 100, 101... 과 같을 때, 3과 100을 인접시켜야 하는 것 아닌가?
하지만 실제로 배치를 해보면 그렇지 않음을 알 수 있다. 높이 정렬 기준으로 인덱스 n의 통나무와 n+1의 통나무를 인접시키고 나면, n-1의 통나무와 n+2의 통나무를 인접시켜야 한다. 그런데 n-1번째 통나무와 n+2번째 통나무의 높이차는 n-1번째와 n+1번째의 높이차보다 크므로, 난이도(높이차)를 줄이지 못한다.
위의 기본 아이디어를 따르면, n개의 통나무가 있을 때 인접하는 통나무 사이의 최대 높이차는 1번과 3번의 높이차, 2번과 4번의 높이차, ... n-2번과 n번의 높이차다. 1번과 2번, n-1번과 n번도 인접하지만, 이것들은 각각 1번과 3번의 높이차, n-2번과 n번의 높이차보다 작으므로 무시해도 좋다. 이를 바탕으로 아래의 코드를 완성했다.
풀이 코드
from sys import stdin
t = int(stdin.readline())
for _ in range(t):
n = int(stdin.readline())
heights = [int(x) for x in stdin.readline().split()]
heights.sort()
max_level = 0
for i in range(2, n):
max_level = max(max_level, abs(heights[i] - heights[i - 2]))
print(max_level)
