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

문제

언니! 똑...똑똑...똑똑! 같이 눈사람 만들래~? ♪

언니 엘자와 동생 안나에게는 N개의 눈덩이가 있다. 각 눈덩이 i (1 ≤ i ≤ N)의 지름은 Hi 이다. 하나의 눈사람은 두 개의 눈덩이로 구성되며, 눈덩이 하나를 아래에 두고 그 눈덩이보다 크지 않은 다른 눈덩이를 쌓아올리는 방식으로 만들 수 있다. 이때, 눈사람의 키는 두 눈덩이 지름의 합과 같다.

엘자와 안나는 눈덩이 N개 중 서로 다른 4개를 골라서 눈사람을 각각 1개씩, 총 2개를 만들려고 한다. 두 자매는 두 눈사람의 키의 차이가 작을수록 두 눈사람의 사이가 좋을 것이라고 믿는다. 우리는 엘자와 안나가 가장 사이좋은 두 눈사람을 만들기 위해서 도와주려고 한다.

주어진 N개의 눈덩이를 이용하여 만들 수 있는 두 눈사람의 키 차이 중 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N (4 ≤ N ≤ 600)이 주어진다.

둘째 줄에는 각 눈덩이 i (1 ≤ i ≤ N)의 지름을 의미하는 정수 Hi (1 ≤ Hi ≤ 109)가 공백으로 구분되어 주어진다.

출력

만들 수 있는 두 눈사람의 키 차이 중 최솟값을 나타내는 정수를 출력하라.

예제 입력 1

5
3 5 2 5 9

예제 출력 1

1

높이가 (2, 5), (3, 5)로 구성된 눈사람 둘을 만드는 것이 최적의 경우 중 하나이다. |7-8| = 1

다른 경우로는 (2, 9), (5, 5)로 두 눈사람을 만드는 경우가 있다. |11-10| = 1

참고답안

import sys
input = sys.stdin.readline

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


def snowman():
    answer = int(1e9)
    for i in range(n - 1):
        for j in range(i + 1, n):
            snow_man_1 = snow[i] + snow[j]
            start = 0
            end = n - 1
            while start < end:
                if start == i or start == j:
                    start += 1
                    continue
                if end == i or end == j:
                    end -= 1
                    continue

                snow_man_2 = snow[start] + snow[end]
                answer = min(answer, abs(snow_man_1 - snow_man_2))
                if snow_man_2 < snow_man_1:
                    start += 1
                elif snow_man_2 > snow_man_1:
                    end -= 1
                else:
                    start += 1
                    end -= 1
    print(answer)

snowman()

1. 눈을 정렬한다.
2. 그리고 앞에서부터 맨 끝 전까지 돌고 그 다음에는 해당 인덱스 다음번부터 snow에서 눈사람을 가져온다.
   1. 문제에서 앞은 작고 뒤는 크다고 했기 때문이다.
3. 그렇게 인덱스 하나는 고정시키고 그거보다 큰거랑 더하면서 end와 start를 조절한다.
   1. i와 j에 해당되면 값을 늘리거나 줄여야 while문을 빠져나갈 수 있다.
4. 그리고 눈사람 1과 start와 end에 해당되는 인덱스 값 눈사람과 비교해서 answer를 업데이트 시킨다.
5. start와 end는 for문에 해당되는게 아니라 i와 j에 해당되는 눈사람과 비교하기위해서 0부터 n-1까지 있기 때문에 조절해서 맞춰준다.
6. 마지막으로 출력한다.