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

https://www.acmicpc.net/problem/20366

공부 날짜 : 2023.02.16
정답 참조 여부 : X

n개의 눈덩이에서 4개의 눈덩이를 골라서 눈사람 2개를 만들때 눈사람 2개의 높이차가 최소인 경우를 찾는 문제이다.

---

투포인터에 익숙하지 않아서 어려웠던 문제.

처음에 떠올린 방법은 안나의 눈사람은 i,j로 고정시키고 엘사의 눈사람은 i~j범위 이내에서 2개를 고르는 방법이였다.

당연히 엘사 눈사람의 모든 경우를 생각하면 O(n^4)이기 때문에 시간초과가 날 것이므로 엘사 눈사람의 경우의 수를 줄이는게 필요했는데

떠올린 방법은 (i+1, j-1), (i+1, i+2), (j-2, j-1)의 조합이였다. 당시에는 굉장히 논리적으로 생각하고 이게 최소가 되는 경우의 수다! 했었는데 지금 생각해보면 이해도 안되고, 왜 저런 생각을 했나 싶을 정도로 멍청한 발상이였다.

결국 모든 경우의 수를 봐야한다는 생각밖에 떠오르지 않아서 다른 사람 코드를 참고했다.

---

답은 비슷했다.

i,j로 고정시키고 엘사의 눈사람은 투포인터로 확인하는 것

하나는 값을 증가시키고 하나는 값을 감소시키며 합이 양수냐, 음수냐를 판단하는데, 양수면 값을 감소시키고 음수면 값을 증가시키는 개념이였다.

투포인터를 정확히 이해하지 못해서 엘사의 눈사람을 (i+1, i+2)에서 i+2를 증가시키고 i+1은 언제 증가 시켜야 하나 이런식으로 접근해서 어려웠던거 같다.

투 포인터는 하나는 증가, 하나는 감소해야 한다는걸 염두해 두고 문제를 풀어야 한다는걸 잘 이해 할 수 있었던 문제

소스코드

import sys
input = sys.stdin.readline
##########################################

n = int(input())

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

snow.sort()

answer = int(10e9)

# 안나의 눈사람을 i,j로 결정
for i in range(n-3):
    for j in range(i+3, n):
        anna_snowman = snow[i] + snow[j]

        # 엘사의 눈사람은 k,l로 결정
        k = i+1
        l = j-1

        # i~j의 사이에서 k == l이 될때까지
        while True:
            if k == l:
                break

            # 계속해서 차이 비교
            elsa_snowman = snow[k] + snow[l]
            check = anna_snowman - elsa_snowman

            # 양수이면 엘사의 눈사람이 커지게
            if check > 0:
                k += 1

            # 음수이면 엘사의 눈사람이 작아지게
            elif check < 0:
                l -= 1

            # 같으면 0출력후 실행 종료
            elif check == 0:
                print(0)
                exit()

            # 절대값 처리후 결과 갱신
            check = check if check > 0 else -check
            answer = min(answer, check)

print(answer)