[PS | 한 번에 맞자!] 백준 20366

0. 문제

같이 눈사람 만들래?

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

---

1. 문제 생각

4개를 뽑아서 대조하는 것으로 먼저 생각해볼 수 있다. 하지만 600C4(5억)는 2초 안에 못 들어오기 때문에 X
일단 N은 600이기 때문에 2초 안에 들어오려면 적어도 N^3까지는 가능하다.

우리가 4개를 뽑아 한 세트를 만든다고 하면 예를 들어 2 3 5 5 일 때 세트는 (1️⃣4️⃣, 2️⃣3️⃣)으로 1번째와 4번째 것이 하나의 세트가 되고 2번째와 3번째 것이 하나의 세트가 되어야만 눈사람끼리 높이가 최소값이 나오는 걸 알 수 있다!
모르겠으면 일일이 해보자

정렬했을 때 우리는 4개를 이용해서 2개씩 짝의 가장 minimum 합을 알 수 있다.
2 3 5 5 9
-> 2 (3 5) 5 
2 2 3 3 4 4
-> 2 (2 3) 3

따라서 NlogN 의 시간을 들여 정렬한 후
for문 2번으로 두 개(i, j)를 선택해 한 세트를 만들고 그 안에서 두 개를 콕 집어(left, right) 한 세트를 만들어 그 최솟갑의 경계값을 찾으면 된다.
이 때 left right로 투포인터를 움직이게 하는 조건은 (i+j) - (left+right)가 음수가 나오면 right를 하나 줄여서 작게 만들어 0 또는 양수가 되도록 하고 .. 양수가 나온다면 그 반대로 해서 어떤 적절한 그 경계값을 찾는 것이다!! 

---

2. 문제 구현

'''
만약 600개에서 4개의 쌍을 찾으면 
600C4
'''

N=int(input())
List=list(map(int,input().split()))
List=sorted(List)

#비교값 init
ans=float('inf')

for i in range(N-3):
    for j in range(i+3, N):
        #위에 i,j로 두 개를 구하고 그 안에서 left, right를 고를 예정
        left = i+1
        right= j-1
        # 비교값 init
        temp = float('inf')
        while left<=right:
            compare=(List[i]+List[j]-(List[left]+List[right]))
            if abs(compare)<ans:
                ans=abs(compare)
            if compare<0: #left+right을 더 작게 만들어야 함
                right-=1
            else:
                left+=1
print(ans)

'''
생각 ?
정렬했을 때 우리는 4개를 이용해서 2개씩 짝의 가장 minimum 합을 알 수 있다.
2 3 5 5 9
-> 2 (3 5) 5 
2 2 3 3 4 4
-> 2 (2 3) 3

'''

---

3.
아이디어 스스로 생각했는가? △
한 번에 풀었는가? O