백준 28703

<더블 잇>

난이도 : 골드 3

1. 백준 문제
   28703

2. 코드 알고리즘

• heap 사용
  우선순위 큐

• 최솟값을 고정
  후보 : A_i, 2A_i ... 중에서만 가능
  v는 max(A_1, ..., A_n) 이하만 가능 즉, 기존 배열에서의 최댓값 이하만 가능
  //놓친 부분 (최솟값을 정할 수 있는 boundary가 있다!)
  

2-2. 슈도 코드

28703 슈도코드

N 입력받기
A 배열 입력받기 


우선순위 큐에 넣기(heap)
min을 힙의 최솟값으로 설정하기
최댓값 = bound 설정
while min<bound:
	최솟값 get하고 v로 설정하기	
	최댓값 출력하고 최대-최소 = min 설정하기(기존의 min 비교하기)
	최솟값 v를 2배 하고 다시 우선순위 큐에 넣기
	max 초기화 해주기(최솟값 2배가 현재 max보다 커질수도 있으므로)

최솟값 min 출력

3. 코드

• 나의 답안

최댓값을 고정해서 최솟값을 최댓값 근처인 값들로 설정한다. 최댓값과 다른 원소들의 값이 비슷하도록 설정한 후 구한 차이가 정답이다

-> 하지만 차이가 최소가 되는 경우를 수학적으로 정의할 수 없다. 또한, 최댓값을 고정할 수 없으며 변경가능하다(2*A_i로)

따라서 boundary를 설정하고 경계까지 프로그램을 돌려 가장 작은 차이값을 찾는 문제이다.

#c

import sys
import math
input = sys.stdin.readline

N = int(input())
A = list(map(int, input().split()))

def merge_sort(arr):
    if len(arr) < 2:
        return arr

    mid = len(arr) // 2
    low_arr = merge_sort(arr[:mid])
    high_arr = merge_sort(arr[mid:])

    merged_arr = []
    l = h = 0
    while l < len(low_arr) and h < len(high_arr):
        if low_arr[l] < high_arr[h]:
            merged_arr.append(low_arr[l])
            l += 1
        else:
            merged_arr.append(high_arr[h])
            h += 1
    merged_arr += low_arr[l:]
    merged_arr += high_arr[h:]
    return merged_arr

#정렬된 A
A = merge_sort(A)

max_A = A[-1] #마지막 원소가 가장 큰 원소

def findMinDiff():
    B=[0]*N
    for i in range(N-1):
        #A 원소 다 최댓값 근처로 바꾸기
        id = int(math.log2(max_A/A[i]))
        a = A[i]*(2**id)
        b = A[i]*(2**(id+1))
        if abs((max_A-a)) > abs((max_A-b)): #b가 차이가 더 작은 경우
            B[i] = b
        else:
            B[i] = a
    B[-1] = max_A
    B=merge_sort(B)
    return B[-1]-B[0]

min_re = sys.maxsize
for i in range(10):
    t = findMinDiff()
    result = min(t, min_re)

print(result)

• 해설참고 답안

#28703
#https://www.acmicpc.net/problem/28703

import sys
from heapq import heappop, heappush

input = sys.stdin.readline

N = int(input())
A = list(map(int, input().split()))

heap=[]
max_h=0 #항상 주어지는 수는 양수

for i in range(N):
    heappush(heap, A[i])
    max_h = max(max_h, A[i])

v = heap[0]
curmax = max_h
min_diff = max_h - v

while heap[0] <= max_h: #최대 나올수 있는 min이 max_h까지 라는 거지, 그전에 min_diff가 나올 확률 큼
    v = heappop(heap) #heap[0] 의미
    min_diff = min(min_diff, curmax - v)
    heappush(heap, 2*v) #이때 넣은 2*v가 max보다 커질경우 2*v를 max로 인정(새로운 max가 등장할경우)
    curmax = max(curmax, 2*v)

print(min(min_diff, curmax-heap[0]))

4. 코드 후기

어렵다,,, 나의 랭킹은 거짓이였어,,,
(랭킹이 골드라 해서 골드 문제를 풀수 있다는 얘기가 아니다!! 골드 문제를 만져봤다는 얘기다!!)
처음에 도전해본 나의 답안은 최댓값을 고정하고 최솟값을 최댓값 근처로 올리는 아이디어였는데 그경우는 주어진 테케에만 적합(과대적합,,)
결국 여러번 프로그램 돌려 최솟값을 직접 찾는 문제 => 그래서 경계를 정하는 아이디어가 중요!!