[백준 - Python] 11497. 통나무 건너뛰기 (그리디)

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

11497번: 통나무 건너뛰기

 

코드

import sys

input = sys.stdin.readline

t = int(input())
for _ in range(t):
    n = int(input())
    answer = [0 for i in range(n)]
    num = list(map(int, input().split()))
    num.sort()
    front = 0
    back = n-1
    tmp = 0
    for i in range(n):
        if tmp == 0:
            answer[front] = num[i]
            front += 1
            tmp = 1
        else:
            answer[back] = num[i]
            back -= 1
            tmp = 0

    sub = []
    for i in range(n-1):
        sub.append(abs(answer[i] - answer[i+1]))
    print(max(sub))

 

통나무를 오름차순 정렬하면 처음과 끝 통나무의 높이 차가 크긴 해도

그 사이의 모든 통나무들끼리의 높이차가 최소가 된다고 생각을 일단 했다.

근데 아무래도 처음과 끝 통나무의 높이 차가 엄청나게 크면

아무리 그 사이 모든 통나무들끼리의 높이차가 최소가 되도 그걸 상쇄할만큼 커질 수도 있기 때문에

단순히 오름차순 정렬을 하는 것이 최소 난이도를 만들 수 없다고 판단했다.

 

각 통나무를 적절하게 섞어서,

처음과 끝 통나무의 높이차도 크지 않게 하려면,

어떻게 정렬해야 할까 고민하다가

통나무 길이가 작은 것부터 순차적으로 리스트의 앞 뒤에 번갈아 저장을 하는 방식이

최선일 것이라 생각했고 그대로 구현을 해서 통과를 했다.

 

코드는 위에서 설명한 바와 동일하게 직관적으로 구현했다.

 

다른 분들의 코드를 살펴보니

나와 아이디어의 핵심 내용은 비슷한데

살짝 다른 관점으로 아이디어를 생각해서

코드의 줄 수를 줄였다.

 

내 아이디어, 즉 가장 큰 수를 기준으로 양쪽에 점점 작게 배치를 하면

결국 인접하는 통나무는 인덱스 값이 2씩 차이나게 된다.

 

for i in range(int(input())):
    n = int(input())
    timbers = sorted(list(map(int, input().split())))
    level = 0
    for i in range(2, n):
        level = max(level, timbers[i]- timbers[i-2])
    print(level)

 

따라서 위와 같은 간결한 풀이가 가능하다.

 

 

참고 자료

https://namhandong.tistory.com/100