백준 20366 같이 눈사람 만들래? (python)

아이디어

브루트포싱기법이 필요하긴 하지만

복잡도를 신경 안쓴다면 O(N^4) 풀이가 생각난다.

근데 그럼 안될거같다.

O(N^3)으로(가능하다면 그 이하로) 풀 순 없을까?

이런건 이분탐색(+ 중간에서 만가기)이 필요하긴 했는데 생각이 잘 안난다.

그래도 일단 2개를 뽑아서 만들수 있는(눈사람하나를 만들 수 있는) 경우의 수를 다 저장해보면 뭐라도 생각날 것 같다.

 

풀이

일단 2개를 뽑아서 눈사람을 만들자.

가능한 모든 nC2개의 경우를 보자.

눈뭉치를 하나 재사용 가능하다면 정렬시키고 순회하며 그냥 양옆의 값만 보고 그중 최소를 가져오면 된다.

하지만 눈뭉치는 한번만 쓸 수 있다.

그래서 중복체크를 해야한다.

for i in range(N):
    for j in range(i + 1, N):
        if i == j:
            continue
        tmp = arr[i] + arr[j]
        data.append((tmp, i, j))

그래서 무엇을 썻는지 알기위해 2개를뽑을 때 눈뭉치 2개의 합 뿐만아니라 무엇을 썻는지도 저장한다.

그래서 그걸 정렬했다 치자.

근데 중복을 신경안썻을땐 양옆만 본 것 처럼 이번에도 무슨 드라마틱한 테크닉이 필요할까 싶다.

우린 결론적으로 정렬한 배열에서 눈사람하나를 골랐을 때 그 근처에 있는 다른 눈사람들이 i,j 썻는지 안썻는지만 보면 된다.

그건 비효율적이지 않다

(i,i+1) , (i,i+2), .... , (i,N)

(j,j+1), (j,j+2), ...., (j,N) 이 눈사람들만제외하면 된다.

많아봐야 1000개보다 조금만 더 체크하면 중복 없는 것이 나올 것이다.

즉 a번째 눈사람을 골랐을때 a+1번부터 N까지 순회하며 중복없는 것이 나오면 그것과 이어주고 break

a-1번부터 0까지 순회하며 중복없는 것이 나오면 그것과 이어주고 break 

가능한 모든 경우에 대해 최소를 구해주면 된다.

 

코드

import sys

input = sys.stdin.readline

# 하나의 눈사람은 두 개의 눈덩이로 구성되며,
# 눈덩이 하나를 아래에 두고 그 눈덩이보다 크지 않은 다른 눈덩이를 쌓아올리는 방식으로 만들 수 있다.
# 이때, 눈사람의 키는 두 눈덩이 지름의 합과 같다.
N = int(input())
arr = list(map(int, input().split()))
data = []
for i in range(N):
    for j in range(i + 1, N):
        if i == j:
            continue
        tmp = arr[i] + arr[j]
        data.append((tmp, i, j))
ans = float('inf')
data.sort()


def yes(a, b, c, d):
    if a == c:
        return False
    if a == d:
        return False
    if b == c:
        return False
    if b == d:
        return False
    return True


for i in range(len(data)):
    val1, a, b = data[i]
    for j in range(i - 1, -1, -1):
        val2, c, d = data[j]
        if yes(a, b, c, d):
            ans = min(ans, abs(val1 - val2))
            break
    for j in range(i + 1, len(data)):
        val2, c, d = data[j]
        if yes(a, b, c, d):
            ans = min(ans, abs(val1 - val2))
            break
print(ans)