728x90
반응형
문제 바로가기
문제:
언니 엘자와 동생 안나에게는 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로 탈출한다.
반응형
댓글