[백준][정렬] 11497 - 통나무 건너뛰기

문제

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

11497번: 통나무 건너뛰기

문제 풀이 방식이 독특해 포스팅하게 되었다.

이 문제는 기본적으로 정규 분포 형태를 띄게 가운데에 제일 높은 수를, 
그 이후 양쪽에 낮은 숫자들을 배치해가면 차이가 최소인 형태를 얻을 수 있는걸 이용해서 풀 수 있다.

 

풀이

import sys
input = sys.stdin.readline

for _ in range(int(input())):
  N = int(input())
  arr = list(map(int, input().split()))
  arr.sort(reverse=True)
  C = N // 2

  result = [0] * N
  result[C] = arr[0]

  for i in range(1, N):
    if i % 2 == 1:
      result[C - i // 2 - 1] = arr[i]
    else:
      result[C + i // 2] = arr[i]
  
  M= 0
  for i in range(N):
    L = abs(result[i] - result[(i + 1) % N])
    M = max(M, L)
  print(M)

 

다른 풀이

import sys
input = sys.stdin.readline

for _ in range(int(input())):
  N = int(input())
  arr = list(map(int, input().split()))
  arr.sort()

  M = 0
  for i in range(N - 2):
    L = abs(arr[i] - arr[i + 2])
    M = max(M, L)
  print(M)

풀이 해설을 통해 이 방법도 알게 되었는데

잘 이해되지는 않지만 내가 이해한바에 의하면

 

첫 번째 풀이를 통해 얻어낸 result는 내림차순으로 정렬된 arr에 대해 

0	1	2	3	4	5	6
arr[5]	arr[3]	arr[1]	arr[0]	arr[2]	arr[4]	arr[6]

이런 형태를 띄게 된다.

근데 가운데 기준 |arr[1] - arr[0]|과 |arr[0] - arr[2]|를 비교할 때

셋 중 제일 큰 수 arr[0]과 제일 작은 수 arr[2]의 차이가 제일 크게 된다. 따라서, 위의 두 방법을 생략할 수 있다.

나머지 (abs로 묶었다 생각하고)

arr[5] - arr[3], arr[3] - arr[1], arr[2] - arr[4], arr[4] - arr[6]은
첫 번째 풀이에서 마지막에 for문을 돌릴 때 계산하는 것과 일치한다.

 

그럼 형태가 아래와 같아지게 되는데

abs(arr[0] - arr[2])
abs(arr[1] - arr[3])
abs(arr[2] - arr[4])
abs(arr[3] - arr[5])
abs(arr[4] - arr[6])

이 중 최대값을 구하면 되니 코드로 나타내면 위의 풀이 방법과 같아지게 된다.

 

더 쉽게 이해해보려 여러 해설을 찾아보았는데, 

인접한 세 통나무 중 가운데 통나무를 제외하는거라는 등 다 이해를 못해서 내 나름대로 위와 같이 이해했다.

 

정리

어쨋든 첫 번째 풀이 방법을 유추해내는 것만으로도 원하는 시간복잡도로 문제를 풀 수 있으니

이런 풀이 방법이 있었다는 걸 짚고 넘어가면 좋을 것 같다.