[Python] 21344번 Hot Spring

 

 

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

21344번: Hot Springs

---

 

22/11/15

 

 

실랜디를 하다가 만난 문제로, 내가 전형적으로 약한 알고리즘이어서 문제를 접근하기가 조금 힘들었었다.

---

 

문제 접근 방식:

 

 

외국어 문제이기 때문에, 번역을 하자면 다음과 같다.

아이슬란드는 나라 전체의 열과 전력의 대부분을 공급해주는 지질학적 운동으로 유명하다.
또한, 온천으로 즐거움을 가져다준다.
칼레는 아이슬란드의 유명한 온천 중 한 곳을 방문한다.
이 온천은 $n$개의 분천이 있으며, $i$번째 분천은 $t_i$의 온도를 가지고 있다.
비록 더 따뜻한 곳에서 충분히 오래동안 머무는 것이 쉬는 것이지만, 칼레는 너무 빠듯한 스케줄 탓에 모든 분천에 마다 빠르게 몸을 담갔다 빼고 싶어 한다.
알다시피, 뜨거운 목욕의 장점은 뜨거운 물과 찬물의 대조이다.
때문에 이 장점을 최대한 활용하고 싶기에, 칼레는 다음 분천과의 온도 차가 증가하도록 하는 분천의 순서를 정해서 들어가고자 한다.
각 분천의 온도 $t_1, t_2, ... t_n$이 주어질 때, 이를 재배열하여 모든 $2 \leq i \leq n-1$ 에 대해 $|t_{i-1} - t_i| \leq |t_i - t_{i+1}|$ 가 되도록 만드시오.

 

처음에 생각한 방법은 백트래킹이었다.

 

하지만, $n$의 범위가 $2 \leq n \leq 10^5$이기 때문에, 가능한 모든 배열을 백트래킹으로 돌면서 전수 조사하면 너무 오랜 시간이 걸릴 것이라고 생각했다.

 

그래서 다른 방법을 생각해야만 했다.

 

그렇다면, DP는 어떨까라고 생각을 해보니, 마땅한 점화식이 떠오르지도 않았다.

 

예시들을 수직선 위에 나열해보니, 정렬을 사용하는 문제라는 것을 단박에 깨달을 수 있었다.

 

예시를 그림으로 한번 살펴보자.

 

왕복 운동하듯 수를 나열하면 된다.

위의 그림처럼 수를 오름 차순으로 정렬한 뒤, 중간값을 취해서 앞으로 뒤로 왔다 갔다 하듯이 수를 택하게 된다면, 자명하게도 이전의 차이보다 작을 순 없다.

 

다시 말해, 이전 수의 차이보다 다음 수와의 차이가 같거나 클 수밖에 없기 때문에, 이 방식을 사용한다면 모든 $2 \leq i \leq n-1$ 에 대해 $|t_{i-1} - t_i| \leq |t_i - t_{i+1}|$ 가 되도록 재배열할 수 있다.

 

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

# 21344번 Hot Springs
# 실랜디(구성적, 애드 혹, 정렬)
'''
문제 요약:
아이슬란드는 나라 전체의 열과 전력의 대부분을 공급해주는 지질학적 운동으로 유명하다.
또한, 온천으로 즐거움을 가져다준다.

칼레는 아이슬란드의 유명한 온천 중 한 곳을 방문한다.

이 온천은 n개의 분천이 있으며, i번째 분천은 t_i의 온도를 가지고 있다.
비록 더 따뜻한 곳에서 충분히 오래동안 머무는 것이 쉬는 것이지만,
칼레는 너무 빠듯한 스케줄 탓에 각 분천에 마다 빠르게 담갔다 빼고싶어한다.
알다시피, 뜨거운 목욕의 장점은 뜨거운 물과 찬물의 대조이다.
때문에 이 장점을 최대한 활용하고 싶기에, 칼레는 다음 분천과의 온도 차가
증가하도록 하는 분천의 순서를 정해서 들어가고자 한다.

각 분천의 온도 t1, t2, ... tn이 주어질 때, 이를 재배열하여 모든 2 <= i <= n-1
에 대해 abs(t_(i-1) - t_i) <= abs(t_i - t_(i+1)) 가 되도록 만드시오.
'''
import sys
input = sys.stdin.readline

N = int(input())
num_li = sorted(map(int, input().rstrip().split()))
if N % 2 == 0:
    now_idx = N//2 - 1
else:
    now_idx = N//2
ans = []
ans.append(num_li[now_idx])
for i in range(1, N):
    if i%2:
        now_idx += i
    else:
        now_idx -= i
    ans.append(num_li[now_idx])
print(*ans)