4개 원소를 골라서 짝지어서 쌍을 만들어 크기 비교하는 놀라운 방법

20366번: 같이 눈사람 만들래?

 

n개의 눈덩이가 있는데, 2개의 눈덩이를 합쳐서 1개의 눈사람을 만들 수 있다

 

n개중 4개의 눈덩이를 골라 2개의 눈사람을 만들려고 한다

 

이때 눈덩이 크기의 합이 눈사람의 크기라고 할때, 두 눈사람의 크기 차이가 최소가 되도록 하려고 한다

 

최솟값을 구하면?

 

--------------------------------------------------------------------------------------------------------------------------------------------------------

 

n이 최대 600인데 이중 4개를 고르면 600C4로 못해도 600*599*598*597 정도에 근사하는 정도?

 

아무튼 10^8을 가뿐하게 넘는다는거지

 

그러면 어떻게 가능할까

 

여러가지 정렬해보고 별 방법을 강구해봤는데 어렵더라고

 

처음에 모든 가능한 눈사람의 크기를 미리 구해놓는다

 

모든 i,j쌍에 대해 H[i] + H[j]가 눈사람의 크기

 

이때 핵심은 (H[i]+H[j],i,j)로 해당 크기를 구성하는 인덱스도 같이 저장해두자

 

n = int(input())

H = list(map(int,input().split()))

A = []

for i in range(n-1):

    for j in range(i+1,n):

        A.append((H[i] + H[j],i,j))

 

 

그러면 이 배열 A를 정렬하면 눈사람의 크기 순으로 정렬된다

 

그러면 눈사람 크기 차이의 최솟값은?

 

정렬된 배열에서 인접한 원소끼리 차이가 최솟값이 된다

 

이때 중요한 점은 두 원소를 구성하는 4개의 인덱스가 중복되어서는 안된다 

 

왜냐하면 4개를 중복없이 골라야하니까

 

당연하지만 모든 i = 0,1,2,..,len(A)-2에 대해 검사해야한다

 

가장 작은 두 원소끼리 차이가 최소라는 보장은 없거든

 

[1,4,6,6,7] 이러면 i = 0에 대해서만 하면 3이지만, 사실 6 - 6 = 0이 최소잖아

 

A.sort()

answer = 10**18

for i in range(len(A)-1):

    a,x,y = A[i]
    b,z,w = A[i+1]

    ind = set([x,y,z,w])

    if len(ind) == 4:

        if answer > b-a:

            answer = b-a

print(answer)