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

20366번: 같이 눈사람 만들래?

 

문제

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

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

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

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

입력

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

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

출력

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

코드

n = int(input())
diameter = sorted(list(map(int, input().split())))
ans = int(1e9)

# 두 눈사람의 키차이 : (1,4)-(2,3)
# 큰 눈사람 고정
for s in range(n-3):
    for e in range(s+3, n):
        l, r = s+1, e-1
        while l <= r:
            diff = (diameter[s]+diameter[e])-(diameter[l]+diameter[r])
            if diff == 0:
                print(0)
                exit()
            elif diff > 0:
                l += 1
            else:
                r -= 1
            if abs(diff) < ans:
                ans = abs(diff)
            
print(ans)

오름차순 정렬되어 있는 눈덩이 배열에서 4개를 뽑는다고 하자.

(1,2,3,4) 눈덩이를 뽑아서 2개의 눈사람을 만들 때 두 눈사람의 키차이가 최소가 되는 조합은 (1, 4), (2, 3)이다. 이 점을 이용하여 (1,4) 눈사람의 크기는 고정해놓고 (2,3) 눈사람의 크기를 투포인터를 이용하여 조절해가며 최소값을 찾는다.

 

1. (1,4) 눈덩이는 for문을 이용하여 각각 s, e를 인덱스 값으로 갖는다. 이때 s의 범위는 0~(n-4), e의 범위는 (s+3)~(n-1)로 잡아야 사이에 (2,3) 눈덩이를 선택할 수 있다.
2. 그리고 (2,3) 눈덩이의 인덱스를 각각 l = s+1, r=e-1로 하여 투포인터를 이용하여 풀이한다.
   • 두 눈사람의 키차이를 저장한 변수인 diff가 0보다 크다면 (2, 3) 눈사람의 크기를 더 키워서 키차이를 줄이기 위해 l의 값을 1 증가시키고 그렇지 않다면 r을 1 감소시켜서 (2,3) 눈사람의 크기를 감소시킨다. 만약 diff가 0이라면 이보다 작을 수는 없으므로 0을 출력하고 프로그램을 종료시킨다.
   • diff의 절댓값이 ans에 저장된 값보다 작다면 ans의 값을 diff의 절댓값으로 갱신한다.