같이 눈사람 만들래?

• 네개의 수의 합/차가 조건을 만족하는 수를 찾는 문제.
• 기본적으로는 수집합 과도 같은 테크닉이다. 모든 페어의 대한 합을 저장해놓고, 이들을 갖고 계산하는 방식으로 시간 복잡도를 O(n^4)가 아닌 O(n^2)로 줄인다.
• 구해놓은 합들 중에서, 차이가 가장 적은 값들을 찾기 위해서는, 합들을 모두 정렬한 뒤에 인접한 것끼리 비교하면 된다. n^2개의 값들을 정렬해야 하므로 정렬에 O(n^2logn)이 되고, 비교하는 것은 O(n^2)에 처리된다.

"""Solution code for "BOJ 20366. 같이 눈사람 만들래?".

- Problem link: https://www.acmicpc.net/problem/20366
- Solution link: http://www.teferi.net/ps/problems/boj/20366
"""

import itertools


def main():
    N = int(input())  # pylint: disable=unused-variable
    H = [int(x) for x in input().split()]

    snowmans = []
    for i, h_i in enumerate(H):
        snowmans.extend((h_i + h_j, {i, j}) for j, h_j in enumerate(H[:i]))
    answer = min(
        (h2 - h1)
        for (h1, ind1), (h2, ind2) in itertools.pairwise(sorted(snowmans))
        if not (ind1 & ind2))
    print(answer)


if __name__ == '__main__':
    main()