백준 9007번 파이썬 문제풀이(카누 선수)

---

이 문제는 단순히 완전탐색을 할려면 4번의 반복문을 돌아야 한다는 것을 알 수 있다. 하지만 n 이 1000 이기 때문에 최대 2번까지밖에 반복문을 돌 수 있다. 그렇다면 다른 방식으로 접근을 해야 하는데 여기서 생각할 수 있는 것이 투포인터 이다. 따라서 이 문제의 접근 방식은 4개의 카누선수 배열을 2개씩 나눠서 반복문을 돈 후 각각 두개의 배열에 담는다. 그리고 투포인터를 두개의 배열로 도는 것이다. 그렇게 한다면 시간초과없이 해당 문제를 해결할 수 있다.

(단, 파이썬으로 제출할 경우 무조건적으로 시간초과가 발생하니 파이파이3로 제출하자.)

T = int(input())

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

    new_arr1 = []
    new_arr2 = []

    # 각각의 카누 선수 정보 4개중 두개씩 조합하여 합을 새로운 리스트에 담는다. 
    for i in range(n):
        for j in range(n):
            new_arr1.append(weights[0][i] + weights[1][j])
            new_arr2.append(weights[2][i] + weights[3][j])

    # 투포인터를 돌기위해 정렬
    new_arr1.sort()
    new_arr2.sort()

    # 투포인터를 돈다.
    s = 0  # 시작포인터
    e = len(new_arr1) - 1  # 끝포인터
    result = new_arr1[s] + new_arr2[e]  # 가장 근접한 카누선수의 몸무게를 출력할 변수
    while s <= len(new_arr1) - 1 and e >= 0:

        if new_arr1[s] + new_arr2[e] == k:
            result = new_arr1[s] + new_arr2[e]
            break
        elif abs(k - result) >= abs(k - (new_arr1[s] + new_arr2[e])):
            if abs(k - result) == abs(k - (new_arr1[s] + new_arr2[e])):
                result = min(result, (new_arr1[s] + new_arr2[e]))
            else:
                result = new_arr1[s] + new_arr2[e]

        if new_arr1[s] + new_arr2[e] > k:
            e -= 1
        else:
            s += 1

    print(result)