코테/BOJ

백준 11497 [통나무 건너뛰기] 파이썬

동 캄 2022. 9. 5. 08:25
반응형

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

 

11497번: 통나무 건너뛰기

남규는 통나무를 세워 놓고 건너뛰기를 좋아한다. 그래서 N개의 통나무를 원형으로 세워 놓고 뛰어놀려고 한다. 남규는 원형으로 인접한 옆 통나무로 건너뛰는데, 이때 각 인접한 통나무의 높이

www.acmicpc.net

#백준 11497
import sys
from collections import deque
tc=int(sys.stdin.readline())
for _ in range(tc):
    dq=deque([])
    n=int(sys.stdin.readline())
    lst=list(map(int,sys.stdin.readline().split()))
    lst.sort()
    for i in range(n):
        if i%2==0:
            dq.append(lst.pop())
        else:
            dq.appendleft(lst.pop())
    M=0
    for i in range(n-1):
        M=max(M,abs(dq[i]-dq[i+1]))
    M=max(M,abs(dq[0]-dq[-1]))
    print(M)
#백준 11497 다른풀이

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)

그리디하게 해결하였다.

반응형