[Python] 백준 20366번 풀이

우선 이 문제는 두 포인터를 활용한 문제다.

두 개의 눈사람 키 차이 중 최솟값을 구하는 문제이다.

문제 풀이를 보고 이해가 안 가는 부분이 있었는데, 

a, b와 사이엔 최소 2개의 원소가 있어야 그 안에서 투포인터를 돌려 a, b로 이루어진 눈사람의 키와 차이가 가장 적은 눈사람을 만들 수 있다.

정렬된 배열에서 두 포인터를 돌리므로, a<=x<=....<==y<=b 순으로 되어있다.

내가 의문을 가진 부분은 a<=x<=y<=b 일 때였다.

(a, x)와 (y, b)로 이루어진 두 눈사람의 키 차이가 가장 적을 때 처음에 가정한 a,b로 이루어진 눈사람이 아니게 되어버리는 것이다.

이 문제에서의 중요한 점은 키 차이라는 것이다.

결국에 (a,x) , (y,b)로 눈사람을 만드는 경우, (a, b),(x,y)로 만들었을 때 같은 키 차이를 가진다.

 

다른 풀이를 봐도 내가 가진 의문 말고 a,b 사이에 두 개 이상의 눈덩이만 있어야 한다만 언급하고 내가 가진 의문을 해결하지 못해서 블로그에 써봤다.

import sys


N = int(input())
arr = sorted(list(map(int, input().split())))
ans = sys.maxsize

for i in range(N):
    for j in range(i+3,N):
        s, e = i+1, j-1  
        while s < e:  
            tmp = (arr[s] + arr[e])-(arr[i] + arr[j])
            if abs(ans)>abs(tmp):  
                ans = abs(tmp)  
            elif tmp == 0:   
                ans = 0 
                print(0)
                exit()

            if tmp > 0:  
                e -= 1
            else:  
                s += 1
                
print(ans)