백준 2467 용액

유형 : 투포인터 알고리즘

 

올림피아드 초등부 1번문제

 

문제풀이

 이미 정렬된 배열이 들어온다는 것을 이용한다.

1. 두 포인터 l과 r에 맨 첫 요소와 마지막 요소의 주소를 넣는다.

2-1. l과 r의 합이 양수일 경우에는 r이 더 작아져야하므로 r을 하나 앞으로 옮겨준다.

2-2. l과 r의 합이 음수을 경우에는 l이 더 커져야하므로 l을 하나 뒤로 옮겨준다.

3. 이때, l과 r의 합의 절댓값이 이전에 기억해둔 l과 r의 합의 절댓값보다 작다면 이 값과 l, r값을 기억해둔다.

예시

1. l과 r의 합이 5 이므로 r을 하나 앞으로 당겨준다. 이 때 5와 (-10, 15)를 기억해둔다.

2. l과 r의 합이 -6 이므로 l을 하나 뒤로 옮겨준다. 이때의 합의 절댓값 6은 5보다 크므로 기억해둘 필요는 없다. 이런식으로 진행하다보면 4에서 저장된 -5와 4의 합의 절댓값이 끝까지 살아남게 된다.

5과정 이후에는 l+r이 항상 양수이므로 r이 계속 낮아지다가 l보다 낮아지면 알고리즘이 종료된다.

Python code

import sys
def solution(liq):
    l=0
    r=len(liq)-1
    ans = [abs(liq[l]+liq[r]),(liq[l],liq[r])]
 
    while l<r:
        mix = liq[l]+liq[r]
        if abs(mix) < ans[0]:
            ans[0] = abs(mix)
            ans[1] = (liq[l],liq[r])
        if mix > 0:
            r-=1
        elif mix < 0:
            l += 1
        else:
            return ans[1]
    return ans[1]
 
if __name__== "__main__":
    n = map(int,sys.stdin.readline().split())
    liq = list(map(int,sys.stdin.readline().split()))
    ans = solution(liq)
    print("{} {}".format(ans[0],ans[1]))

후기

리스트만 입력값으로 들어오는줄 알고 21 line을 빼먹었다가 한참을 헤맸다...

 

파이썬으로 푼 사람이 많지는 않지만 1등을 해보는 날이 오다니..

문제 링크

2467번: 용액