[BOJ 2467] 용액(Python)

www.acmicpc.net/problem/2467

2467번: 용액

n=int(input())
liquids=list(map(int, input().split()))

left=0
right=2000000000

while left<=right:
    mid=(left+right)//2
    isClose=False
    for i in range(n):
        start, end=i+1, n-1
        while start<=end:
            mid2=(start+end)//2
            if abs(liquids[i]+liquids[mid2])<=mid:
                isClose=True
                l=(i,mid2)
                break
            else:
                if liquids[i]>=0 and liquids[mid2]>=0:
                    end=mid2-1
                elif liquids[i]<0 and liquids[mid2]<0:
                    start=mid2+1
                elif liquids[i]<0 and liquids[mid2]>=0:
                    if abs(liquids[i])>=abs(liquids[mid2]):
                        start=mid2+1
                    else:
                        end=mid2-1
        if isClose==True:
            break
    if isClose==True:
        right=mid-1
    else:
        left=mid+1

print(str(liquids[l[0]])+" "+str(liquids[l[1]]))

소감: 나에겐 어려워서.. 코드가 매우매우매우매우 더.럽.다 ^^ 제출하고 보니까 다른 분들은 코드 길이가 300B 이런데 난 900B ^^ 구글링 하여 효율적인 방법을 탐색해보았다.

포인트를 몇가지 정리해본다.

 

• 이분탐색 문제이다.

m.blog.naver.com/dyk777/221830988355

BOJ[2467] 용액

이 글 참고할것!!

여기서는 오.름.차.순이라는 조건을 적극적으로 활용한것 같다.

여기서는 양 끝(L끝+R끝) 더한 뒤, 결과값이 

0 이상이 나올 경우: 0쪽으로 가야하니깐 줄여준다, 즉 R을 조금 더 줄임

0 미만이 나올 경우: 0쪽으로 가야하니깐 수를 늘려야함. (e.g -9가 0쪽으로 가려면 +9가 필요함), L을 늘려준다

 

이렇게 간단한 매커니즘으로 해결가능하다.

너무 이분탐색이라는 틀에만 갖혀 해결한것같다.