(Python/🥇5)백준알고리즘 20366번 : 같이 눈사람 만들래?

같이 눈사람 만들래?

문제 바로가기 

 

문제:

언니 엘자와 동생 안나에게는 N개의 눈덩이가 있다. 각 눈덩이 i (1 ≤ i ≤ N)의 지름은 Hi 이다. 하나의 눈사람은 두 개의 눈덩이로 구성되며, 눈덩이 하나를 아래에 두고 그 눈덩이보다 크지 않은 다른 눈덩이를 쌓아올리는 방식으로 만들 수 있다. 이때, 눈사람의 키는 두 눈덩이 지름의 합과 같다. 엘자와 안나는 눈덩이 N개 중 서로 다른 4개를 골라서 눈사람을 각각 1개씩, 총 2개를 만들려고 한다. 두 자매는 두 눈사람의 키의 차이가 작을수록 두 눈사람의 사이가 좋을 것이라고 믿는다. 우리는 엘자와 안나가 가장 사이좋은 두 눈사람을 만들기 위해서 도와주려고 한다.

입력:

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

출력:

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

 

일단 시간초과로 하나 풀어준다.

import sys
from itertools import combinations

sys.stdin = open('/Users/song/Desktop/Python/Python/h.txt', 'r')

n = int(input())
lst = list(map(int, sys.stdin.readline().rstrip().split(" ")))
# 3 5 2 5 9
res = 1e9
for combis in list(combinations(lst, 4)):
    x = sum(combis)
    for combi in list(combinations(combis, 2)):
        res = min(res,abs(abs(x-sum(combi)) - sum(combi)))
print(res)

 

콤비 n 600밖에 안되길래 콤비네이션 해줬는데 역시나 안된다.

600c4를 계산해봤는데 5346164850나온다.53억 1초당 1억이니 53초이다 

 

정렬하고 투포인터가 정석같다.

 

내 아이디어는 정렬을 한 후 left와 right로 길이가 4가 되면 거기 안에서 최솟값을 최신화 한다.

 

import sys

sys.stdin = open('/Users/song/Desktop/Python/Python/h.txt', 'r')

N = int(input())
lst = sorted(list(map(int, sys.stdin.readline().rstrip().split(" "))))

res = 1e9
for i in range(N - 3):
    for j in range(i + 3, N):
        # 밖에 있는 i, j
        left = i + 1;
        right = j - 1
        while left <= right:
            middle_res = (lst[i] + lst[j]) - (lst[left] + lst[right])
            if abs(middle_res) < res:
                res = abs(middle_res)
                if res == 0:
                    print(res)
                    exit()
            if middle_res < 0:
                right -= 1
            else:
                left += 1
print(res)

 

큰 투포인터 하나와 그 안에 투포인터를 구해 서 비교해주면된다.

0일때는 그냥 끝내면 되니깐 Exit로 탈출한다.