[백준/Python] (S1) 통나무 건너뛰기 - 11497

Baekjoon Online Judge의 11497번 통나무 건너뛰기 문제의 Python 풀이입니다.

11497번: 통나무 건너뛰기

💻코드

T = int(input())
for _ in range(T):
    N = int(input())
    heights = list(map(int, input().split()))
    heights.sort()  # 통나무의 높이를 오름차순으로 정렬

    # 정렬된 리스트를 두 부분으로 나누어 하나는 순서대로, 다른 하나는 역순으로 하여 원형으로 배치
    new_heights = heights[::2] + heights[1::2][::-1]

    # 인접한 두 통나무 사이의 높이 차이의 최댓값을 계산
    max_diff = max(abs(new_heights[i] - new_heights[i-1]) for i in range(N))

    print(max_diff)

🧠풀이

문제를 해결하기 위해 주어진 통나무의 높이를 먼저 오름차순으로 정렬한다. 정렬된 통나무들을 최소 난이도로 원형으로 배치하기 위해서는 높이가 서로 가까운 통나무들을 인접하게 배치해야한다. 이를 위해 통나무를 홀수 인덱스는 그대로 두고, 짝수 인덱스는 역순으로 배치하여 최소 난이도를 달성할 수 있는 배열을 생성한다. 이 배열에서 인접한 통나무들 간의 높이 차의 최댓값을 구하면 그것이 주어진 통나무 배열의 난이도가 된다.

🤔느낀 점

Greedy