백준 11497. 통나무 건너뛰기 - 문제풀이 (Python/파이썬)

🔎 11497번. 문제 보기
https://www.acmicpc.net/problem/11497

💡 문제 풀기 전
오늘의 교훈, 글이 많다고 이상한 그림이 있다고 겁먹지 말고 차근차근 다가갈 것..!😉💪 찾아야 하는 규칙은 예상보다 굉장히 간단했다!

📋 코드 보기

from sys import stdin

for i in range(int(stdin.readline())):
    X = int(stdin.readline())
    nums = sorted(list(map(int, stdin.readline().split())))
    level = 0
    for j in range(2, X):
        level = max(level, abs(nums[j] - nums[j - 2]))
    print(level)

🥕 코드 풀이 및 관련 개념

문제풀이 아이디어

목표는 난이도를 가장 쉽게 만들자!

사실상 일반적으로는 그냥 오름차순 또는 내림차순으로 정렬해서 가장 큰 차를 출력하면 그것이 난이도가 될텐데, 여기는 조건을 하나 추가했다.

첫 통나무와 마지막 통나무는 인접한다.

즉 [ 1, 3, 5, 6, 8 ] 로 하더라도 이 배열의 난이도는 | 8-1 | = 7이 된다는 것이다.

그래서 고민 끝에, 가장 큰 수를 가운데로 몰고 양쪽으로 흩어질수록 수가 작아지도록 하자! 라는 생각을 떠올렸다.

일단 위의 예시를 그대로 가져가자면

[ ?, ?, 8, ?, ? ] 로 시작을 하면 된다.
이제 양쪽으로 수를 줄여야 하는데 여기서 어떤 기준으로 줄이지? 라는 고민을 꽤나 많이 했다.

일단 8 양옆으로 8과 가장 가까운 수들을 놔줘야 한다. (오른쪽에 오느냐 왼쪽에 오느냐는 사실 뒤집으면 똑같아서 신경쓰지 않았다.

[ ?, 6, 8, 5, ? ]

음.. 여기서 난이도를 가장 낮게 만드려면 남은 수에서 다시 큰 수를 붙여줘야겠다!
라고 생각했고, 이번 예시에서는 8 다음으로 큰 수(6)을 왼쪽에 배치했기 때문에 왼쪽을 기준으로 시작했다.

[ 3, 6, 8, 5, 1 ]

완성!!

이걸 코드로 구현한 부분이

for j in range(2, X):
        level = max(level, abs(nums[j] - nums[j - 2]))

여기다 ㅎㅎ

완성된 것도 그렇고, 다른 예시를 적용해봐도
[ 1, 3, 5, 6, 8 ]일 때
1 - 5
3 - 6
이렇게 연결이 되어있기 때문에 위에처럼 코드를 짜면 자동으로 계산이 착착 된다!