백준 20366 - 같이 눈사람 만들래? [Python]

www.acmicpc.net/problem/20366

 

[사용한 알고리즘]

두 포인터

 

[시간복잡도]

O(N^3)

먼저 i번째, j번째 눈덩이 두개를 정해서 눈사람1의 높이를 정해준다.

이를 기준으로 두번째 눈사람을 두 포인터를 이용하여 구할 수 있다. 더 빠른 방법이 있을 것 같지만 잘 모르겠다.

n = int(input())
li = sorted(list(map(int, input().split())))
ans = 10**10

for i in range(n):
    for j in range(i+1, n):
        s1 = li[i] + li[j] # 눈사람1의 높이

        a = i
        b = n-1
        while True:
            # li[i], li[j]는 이미 사용한 눈덩이이므로 넘겨줘야 한다.
            while a == i or a == j:
                a += 1
            while b == i or b == j:
                b -= 1

            if a >= b:
                break
            
            s2 = li[a] + li[b] # 눈사람2의 높이
            if s1 < s2:
                ans = min(ans, s2-s1)
                b -= 1
            elif s1 >= s2:
                ans = min(ans, s1-s2)
                a += 1
print(ans)

오타 지적 감사합니다