백준[ 11497 | Python ] 통나무 건너뛰기

문제

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

시도

처음에는 이 문제가 그리디인지 의심하다가 풀이 방법을 떠올렸다.
가장 큰 통나무를 기준으로 그 다음으로 작은 값을 왼쪽, 오른쪽에 채우는 방식으로 해결해야겠다고 생각했고, 이 때문에 그리디, 정렬 문제라고 생각이 들었다.
이를 직접 구현하다가 너무 오랜 시간이 걸려 다른 이의 코드를 참고했다.
참고한 코드 - https://namhandong.tistory.com/100

풀이

for _ 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, abs(timbers[i]-timbers[i-2]))
    print(level)

생각 & 정리

level = max(level, abs(timbers[i]-timbers[i-2])) 이 코드가 의아했다.
코드 설명을 봤을 때 내 풀이 방법이 맞다고 생각했는데, 이를 구현 하는 코드가 아니었다.
그래서 비교를 해보았는데,
중앙 기준 정렬 ex) [2, 5, 9, 7, 4]
오름차순 기준 정렬 ex) [2, 4, 5, 7, 9]
에서 오름차순 정렬을 기준으로 위 코드에 대입 하여 생각해보았을 때와
중앙 정렬 후 순차적으로 높이 차이를 비교해 보는 것과 크게 다르지 않게 돌아가는 것을 확인할 수 있었다.

문제를 파악하는 것도 중요하지만, 간단한 메모나 손코딩으로 먼저 결과를 생각해보고 풀었다면
직접 구현까지 생각하지는 않았을 것 같다. 먼저 생각 해보는 습관을 더 길러야 할 것 같다.