IQ
면접 대비시간 제한1초메모리 제한64 MB
2n개의 수를 n개의 짝으로 묶어 각 짝의 합 중 최댓값과 최솟값의 차이가 최소가 되도록 할 때, 그 최솟값을 출력한다.
문제
초보 학생 명이 알고리즘 연습에 참가했다. 각 학생은 IQ로 특징지어지며, 번째 학생의 IQ는 이다.
코치는 학생들을 두 명씩 팀으로 나누려고 한다. 각 팀은 팀원 IQ의 합인 팀 IQ로 특징지어진다. 예를 들어 학생 와 가 한 팀이 되면 팀 IQ는 이다. 팀 IQ가 더 큰 팀이 더 강하다.
코치의 생각에는 가장 강한 팀과 가장 약한 팀의 팀 IQ 차이가 최대한 작으면 연습이 훨씬 생산적이다. 가장 강한 팀과 가장 약한 팀의 팀 IQ 차이가 가 되도록 팀을 구성할 수 있는 최솟값 를 구해 코치를 도와라.
입력
첫째 줄에 정수 이 주어진다. ()
둘째 줄에 개의 정수가 주어지며, 번째 정수는 번째 학생의 IQ 이다. (, )
출력
팀 구성이 가능한 최솟값 를 출력한다.