[Python 3] BOJ - 9007 "카누 선수"

 # 문제 링크

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

9007번: 카누 선수

 

 # 풀이

 개인적으로 이 문제의 핵심은 투 포인터라고 생각한다. 왜냐하면 n의 제한이 1000이기 때문에 두 반의 모든 몸무게의 조합을 비교하게 되면 \(1000^2\)만큼 시간이 걸리기 때문이다. 따라서 리스트가 2개가 되고 다시 두 반의 조합을 brute-force하게 구하게 되면 \(1000 ^ 4\)이 걸리기 때문에 시간 초과를 피할 수 없다.

<그림 1. k=6인 경우 예시>

 위 그림 1의 경우를 보자. 현재 i와 j의 합인 sum이 6보다 큼을 알 수 있다. 현재 상태에서 무엇을 해야하나? 가능한 행동은 2가지가 있다. 첫번째는 i를 움직이는 것이고, 두번째는 j를 움직이는 것이다. 당연히 j를 움직여야 한다. 왜냐하면 i를 움직여버리면 (0, 6)의 경우를 찾을 수 없기 때문이다. 따라서, j를 움직여야 한다. 

<그림 2. k=6인 경우 예시>

 위 그림은 j를 왼쪽으로 움직인 이후 결과를 나타낸 것이다. 여기서는 다시 어떻게 해야할까? 여기서는 i를 움직여도, j를 움직여도 상관이 없다. 다만 둘 다 움직이지만 않으면 된다. 왜냐하면, 현재 정렬된 상태이기 때문에 i를 움직인다면 적어도 k 이상인 수가 될 것이며 반대로 j를 움직이면 적어도 k 이하인 수가 될 것이기 때문이다. 그런데 사실은 여기서 멈춰도 상관이 없다. 왜냐하면 우리가 찾는 6에 정확히 도달했기 때문에 더 이상의 탐색을 통해 현재보다 적은 차이를 만들 수 없기 때문이다. 그러나 같은 경우에는 j를 움직인다고 가정해보자

<그림 3. k=6인 경우 예시>

 위 그림 3은 이후 상황을 나타낸다. 현재는 sum이 k보다 작으므로 i을 옮겨야 함이 자명하다. 결국, brute-force보다 투 포인터가 효율적이면서 정답을 구할 수 있는 이유는 탐색을 함에 있어서 k와 현재 조합의 절댓값 거리를 최소화하면서 찾기 때문이다. 즉, k와 현재 조합의 값 차이가 크다면, 그 다음 탐색은 값 차이를 작게하고 반대의 경우 역시 마찬가지로 값 차이를 최소화한 채로 움직이기 때문이다. 값 차이가 최소이기 때문에 절댓값의 차이 역시 최소가 된다.

 그런데 왜 정렬을 해야할까? 이유는 우리가 앞서 전제했던 이동 방식에 있다. 현재 값차이가 큰 경우, 즉 j를 왼쪽으로 옮겨야 하는 경우를 생각해보자. 이 때 j - 1번째 인덱스의 값이 j번째 인덱스보다 작거나 같아야 j번째 부터 n번째 인덱스의 조합을 모두 무시할 수 있기 때문이다. 따라서 투 포인터에서는 정렬이 필수적이다.

 

 # 코드

import sys

# tc : 테스트케이스 수
tc = int(sys.stdin.readline())
for _ in range(tc):

    # 입력부
    k, n = map(int, sys.stdin.readline().split())
    arr = []
    for _ in range(4):
        arr.append(list(map(int, sys.stdin.readline().split())))
        
    # first : 1반과 2반의 조합을 담는 리스트
    # second : 3반과 4반의 조합을 담는 리스트
    first = []
    second = []
    for i in range(n):
        for j in range(n):
            first.append(arr[0][i] + arr[1][j])
            second.append(arr[2][i] + arr[3][j])
            
    first.sort()
    second.sort()
    i = 0
    j = len(second) - 1
    
    # diff : 전체 조합과 k간의 절댓값 차이
    # ans : 그 때의 전체 조합(정답)
    diff = 9876543210
    ans = 9876543210
    
    # 각 포인터가 각각의 범위를 유지한 채 반복
    while i < len(first) and j >= 0:
    
        # 현재 조합의 절댓값 거리가 더 작다면 갱신
        if abs((first[i] + second[j]) - k) < diff:
            diff = abs((first[i] + second[j]) - k)
            ans = first[i] + second[j]
            
        # 같다면 문제 조건에 따라 더 작은 조합으로 갱신
        elif abs((first[i] + second[j]) - k) == diff:
            if ans > first[i] + second[j]:
                ans = first[i] + second[j]
                
        # 값 차이가 크다면 j를 왼쪽으로
        if first[i] + second[j] > k:
            j -= 1
        # 값 차이가 작다면 i를 오른쪽으로
        elif first[i] + second[j] < k:
            i += 1
        # 같다면 탐색 종료
        else:
            break
            
    # 만일 diff가 0이 된다면 while문의 조건을 만족함에도 빠져 나오기 때문에 체크
    if i < len(first) and j >= 0:
        if abs((first[i] + second[j]) - k) < diff:
            diff = abs((first[i] + second[j]) - k)
            ans = first[i] + second[j]
            
   # 정답 출력
    print(ans)