[BOJ/백준] 20366 같이 눈사람 만들래?

N = int(input())

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

arr.sort()


elsa_start = 0
elsa_end = N -1
result = float('inf')

for elsa_start in range(N-3):
    for elsa_end in range(elsa_start+3,N):
        anna_start = elsa_start + 1
        anna_end = elsa_end - 1
        elsa = arr[elsa_start] + arr[elsa_end]
        while anna_start < anna_end:
            anna = arr[anna_start] + arr[anna_end]
            temp = elsa-anna
            if result > abs(temp):
                result = abs(temp)
            
            if temp > 0:
                anna_start += 1
            else:
                anna_end -= 1



print(result)

 

 

첫 풀이는 ELSA와 ANNA로 나누는데, ELSA를 작은것을 1~N-3까지 그리고 큰 눈사람을 3~N 사이의 것을 고르고, 그 사이의 값에서 elsa anna의 격차가 작은걸 구했다.

 

def diffcheck(A,B):
    ss = set()
    ss.update(A)
    ss.update(B)
    if len(ss) == 4:
        return True
    return False
def getDiffHeight(A,B):
    elsa = arr[A[0]] + arr[A[1]]
    anna = arr[B[0]] + arr[B[1]]
    return abs(elsa-anna)
N = int(input())

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

arr.sort()

stack = []

for i in range(N-1):
    for j in range(i+1,N):
        stack.append((i,j))

stack.sort(key=lambda x : arr[x[0]]+arr[x[1]])
result = float('inf')
for i in range(len(stack)-1):
    if diffcheck(stack[i],stack[i+1]):
        result = min(result,getDiffHeight(stack[i],stack[i+1]))


print(result)

두번째 풀이는 다음과 같다. 가능한 좌표의 조합을 다 구하고,

 

그 좌표의 조합에서 나오는 눈사람의 크기를 기준으로 정렬을 해준다.

 

그리고 그 4개의 고른 눈사람 좌표가 다르고, 그 격차가 작으면, 최저값으로 갱신해주는 것이다.