[Python] 9007번 카누 선수

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

9007번: 카누 선수

---

 

23/12/27

 

 

중간에서 만나기(MITM) 연습 문제로 풀었던 문제이다.

---

 

문제 접근 방식:

 

 

전체적인 사고 방식은 이전에 풀었던 중간에서 만나기 기본 문제인 7453번 문제와 같다.

 

이 문제에 대한 해설은 아래와 같다.

 

2024.01.02 - [알고리즘/백준 문제 풀이] - [Python] 7453번 합이 0인 네 정수

[Python] 7453번 합이 0인 네 정수

 

이 문제에 대한 $N$제한은 $1,000$까지 인데, 마찬가지로 그냥 나이브하게 $\mathcal{O}(N^4)$의 시간 복잡도를 지니고 있는 코드를 구현하면 시간 초과를 받을 수밖에 없다.

 

따라서 분할 정복 처럼 그룹을 두 개의 그룹으로 묶어서 생각해서 구현하면 해결할 수 있다.

 

이 문제의 경우 이분 탐색으로 구현해도 잘 통과되었다.

 

구현할 때의 유의할 점은, 특정 값에 가장 가깝도록 하는 몸무게의 합이 여러 가지가 있다면, 그중에서 가장 작은 것을 취하는 것이다.

 

나는 이를 무작정 갱신하기 보단 이전 몸무게의 합보다 더 오차가 적은 새로운 몸무게의 합이 있을 때만 갱신해 주고, 오차는 같은데 몸무게의 합이 더 작은 경우일 때만 갱신해 주도록 코드를 구성했다.

  

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

# 9007번 카누 선수
# 분할 정복
import sys
input = sys.stdin.readline
from bisect import bisect_left, bisect_right
def solve():
    N, K = map(int, input().rstrip().split())
    Class1, Class2 = list(map(int, input().rstrip().split())),list(map(int, input().rstrip().split()))
    Class3, Class4 = list(map(int, input().rstrip().split())),list(map(int, input().rstrip().split()))
    Class12, Class34 = [0 for _ in range(K*K)], [0 for _ in range(K*K)]
    for i in range(K):
        for j in range(K):
            Class12[i*K+j] = Class1[i] + Class2[j]
            Class34[i*K+j] = Class3[i] + Class4[j]
    Class12.sort()
    Class34.sort()
    nearest_val, nearest_err = Class12[0] + Class34[0], abs(N-Class12[0]-Class34[0])
    for i in range(K*K):
        q = Class12[i]
        l = bisect_left(Class34, N-q)
        if l == K*K:
            val1 = q+Class34[-1]
            err1 = abs(N-val1)
            if err1 == nearest_err and val1 < N:
                nearest_err = err1
                nearest_val = val1
            if err1 < nearest_err:
                nearest_err = err1
                nearest_val = val1
        else:
            val1, val2 = q+Class34[l], q+Class34[l-1]
            err1, err2 = abs(N-val1), abs(N-val2)
            if err1 < nearest_err:
                nearest_err = err1
                nearest_val = val1
            if err1 == nearest_err and val1 < N:
                nearest_err = err1
                nearest_val = val1  
            if err2 < nearest_err:
                nearest_err = err2
                nearest_val = val2
            if err2 == nearest_err and val2 < N:
                nearest_err = err2
                nearest_val = val2
    print(nearest_val)
for _ in range(int(input())):
    solve()