백준(BOJ) 2473 세 용액(Python)

문제 내용

 

이분 탐색 문제.

특성값을 받아서 오름차순 정렬하고, 왼쪽에서부터 조합으로 두 개씩 선정한 뒤 둘 중 더 큰 값을 기준으로 더 큰 값들에 대해 이분 탐색을 진행한다.

현재 특성값의 합이 지금까지 최소 특성값의 합보다 작은 경우 세 용액의 값을 수정한다.

이분 탐색의 경계값 수정 조건은 세 용액의 특성값의 합이 0보다 큰지 작은 지이다.

작다면 s=mid+1로 당기고, 크다면 e=mid-1로 당긴다. 이유는 너무나도 자명하다.

 

코드는 다음과 같다.

 

# -*- coding: utf-8 -*-
import sys
from collections import deque
import heapq
import copy
from itertools import combinations
from itertools import permutations
import bisect
import math
#input=sys.stdin.readline
#print=sys.stdout.write
#sys.setrecursionlimit(100000000)

def main():
    ans=10e10
    n=int(input())
    L=list(map(int,input().split()))
    L.sort()
    a=0
    b=0
    c=0
    for i in range(n):
        k=L[i]
        for j in range(i+1,n):
            l=L[j]
            s=j+1
            e=n-1
            while s<=e:
                mid=(s+e)//2
                if abs(k+l+L[mid])<ans:
                    ans=abs(k+l+L[mid])
                    a=k
                    b=l
                    c=L[mid]
                if k+l+L[mid]>0:
                    e=mid-1
                else:
                    s=mid+1
    print(a,b,c)
    
    
    
if __name__ == '__main__':
    # sys.setrecursionlimit(2*10**5+50)
    # threading.stack_size(10**8)
    # threading.Thread(target=main).start()
    main()

 

2467번을 풀고 나서 바로 문제를 풀었는데, 코드를 약간만 바꿔서 풀려고 하다 낭패를 보고 처음부터 다시 풀었다.

pypy로 제출했다.