백준(11497) - 통나무 건너뛰기 Python

백준(11497) - 통나무 건너뛰기

문제풀이: 그리디, 파이썬

통나무간의 높이의 차이 총합이 가장 적으려면 어떤 방식으로 통나무를 놓아야 하는지 탐욕적(Greedy)으로 확인해 봐야한다.

13 10 12 11 10 11 12 의 문제의 예시로 본다면

10 11 12 13 12 11 10 으로 놓아야 한다.

1. 가운데에 큰값을 놓고 양쪽으로 하나씩 높이가 낮은 통나무를 배치하면 된다.
2. 통나무를 내림차순으로 정렬한다.
3. 가장 긴 통나무를 중앙에 놓고, 그 이후로는 정렬된 통나무에서 하나씩 왼쪽, 오른쪽 순서로 배치하면 된다,

import sys
from collections import deque
input = sys.stdin.readline


testcase = int(input())
for _ in range(testcase):
    n = int(input())
    trees = list(map(int, input().split()))
    trees.sort(reverse=True)

    res = deque()
    res.append(trees[0])
    answer = 0
    for i in range(1,n):
        if i % 2 == 0:
            answer = max(answer, res[0] - trees[i])
            res.appendleft(trees[i])
        else:
            answer = max(answer, res[-1] - trees[i])
            res.append(trees[i])
    answer = max(answer, abs(res[-1] - res[0]))
    # print(res)
    print(answer)