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

백준 20366 - 같이 눈사람 만들래?

시간 제한 2초, 메모리 제한 1024MB

# 조건

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

입력

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

출력

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

# 접근 방법

• 우선 원소의 순서를 변경해도 무방하므로 정렬을 해준다.
• 각 눈사람의 키 차이를 정하기 위하여 투 포인터를 사용해줄 건데, 여기서 중요한 점은
  • 두 눈사람의 키 차이가 최소가 되기 위해서는 연속된 값을 선택하는 것이 아니라 한 눈사람 사이의 값을 선택하는 것이 최소가 된다.
  • 즉, 예제와 같이 2 3 5 5 가 있다면 2+3 과 5+5가 아닌 2+5 와 3 + 5 를 선택하는 것이 각 눈 사람의 키가 최소가 되는 선택이다.
• 따라서, left와 right를 선택하기 이전에 한 눈사람의 키를 특정할 반복문 범위를 i+3을 해주어 가운데 최소 2개의 원소가 존재하게 만들어 준다.

import sys
input =sys.stdin.readline


N = int(input())

nums = [*map(int, input().split())]
nums.sort()
result = float('inf')

# 두 눈사람의 키가 최소가 되기 위한 선택
# 2 3 5 5 가 있을 때 2,3 과 5,5 가 아닌 2,5와 3,5 처럼
# 첫 눈사람이 선택한 두 수 사이에 있는 2개의 값을 나머지 눈 사람이 선택하는 경우가 최소가 된다.
flag = True
for i in range(N):
    for j in range(i+3, N):
        left = i+1
        right = j-1
        while left < right:
            first = nums[j] + nums[i]
            second = nums[right] + nums[left]
            temp = second - first
            if abs(temp) < result:
                result = abs(temp)

            # 현재 값이 0보다 크다면 right -= 1
            if temp > 0:
                right -= 1
            elif temp < 0:
                left += 1
            else:
                result = 0 
                flag = False
                break
        if not flag:
            break
    if not flag:
        break

print(result)

• 또한, 시간을 조금 더 줄이기 위해 고민하다가 눈사람의 합을 미리 구하는 방법을 생각하였다.
  • 입력을 받으며 첫 눈 사람의 합을 인덱스 i, j 값과 함께 기록한 후 정렬해준다.
• 이후, 미리 구해둔 값을 2개씩 꺼내며, 만약 4개의 좌표가 모 다르고 result 값보다 작다면 갱신해준다.

import sys  
sys.stdin = open('input.txt')  
input =sys.stdin.readline  

N = int(input())  
nums = [*map(int, input().split())]  

# 미리 차이를 구해서 좌표와 함께 정렬해주기  
diff = sorted([nums[i]+nums[j], i, j] for i in range(N) for j in range(i+1, N))  

result = float('inf')  
# 2개의 눈사람이 가질 수 있는 키는 동일하므로  
# 2개씩 꺼내서 4개 좌표 모두 다르고 최소라면 갱신  
for i in range(len(diff)-1):  
    first, fi, fj = diff[i]  
    second, si, sj = diff[i+1]  
    if fi == si or fj == sj or fi == sj or fj == si:  
        continue  
    # 2번째 값이 무조건 크거나 같기 때문에 절댓값 해줄 필요없음  
    result = min(result, second-first)  

print(result)

 

• 2배의 메모리가 들었지만, 5배 정도의 속도 이득을 볼 수 있었다.
• 메모리 여유가 필요한지, 시간 여유가 필요한지에 따라 필요한 아이디어와 자료 구조를 사용하는 것이 정말 중요해 보이는 문제였다!