[백준] 9007번 - 카누 선수 (파이썬)

https://www.acmicpc.net/problem/9007

 

# 카누 선수

import sys
input = sys.stdin.readline

T = int(input())
for _ in range(T):
    k, n = map(int, input().split())
    arr = []
    for _ in range(4):
        arr.append(list(map(int, input().split())))

    one, two = set(), set()
    for idx in range(0, 4, 2):
        for x in arr[idx]:
            for y in arr[idx+1]:
                one.add(x+y) if idx == 0 else two.add(x+y)
    one = sorted(list(one))
    two = sorted(list(two))

    # 투포인터
    result = 0
    diff = sys.maxsize
    i, j = 0, len(two)-1
    while i < len(one) and 0 <= j:
        temp = one[i]+two[j]-k
        if abs(temp) < diff:
            diff = abs(temp)
            result = temp + k
        elif abs(temp) == diff:
            result = min(result, temp+k)
        if temp < 0:
            i += 1
        elif temp > 0:
            j -= 1
        else:
            break

    print(result)

 

투포인터, 이분탐색, bisect
1. 입력을 받고 i, j 를 설정 (i = one을 왼쪽부터, j = two를 오른쪽부터)
2. 투포인터
    - 범위 내이면 반복
    - 두 수의 합에서 k를 빼기
    - dff보다 차이가 적으면 diff수정, result 초기화
    - diff랑 같으면, 더 작은 값으로 수정
3. result 출력