백준 2467 용액

haruponea·2021년 4월 3일
0

BOJ

목록 보기
33/41

문제 링크https://www.acmicpc.net/problem/2467

풀이
투포인터 기법으로 풀 수 있는 문제였습니다. 처음에 가능한 모든 합의 경우의 수를 구하고 정렬시킨 후 이진탐색으로 찾는 방법을 생각했었는데 경우의 수를 구하는데 걸리는 시간이 100,000^2 = 10,000,000,000 백억번 연산을 해야해서 TLE가 나올 것같아 투포인터로 풀었습니다. 양 끝에 포인터를 위치시킨 후 sum의 부호에 따라서 포인터를 시동시키면 되는 문제였습니다.

Python

import sys
input = sys.stdin.readline
n = int(input())
nums = list(map(int, input().split()))
left, right = 0, n-1
ans = (left, right)
while left < right:
    sum = nums[left] + nums[right]
    ans = (left, right) if abs(nums[ans[0]] + nums[ans[1]]) > abs(sum) else ans
    if sum < 0:
        left += 1
    elif sum > 0:
        right -= 1
    else:
        break
print(nums[ans[0]], nums[ans[1]])

0개의 댓글