BOJ 9007번 카누 선수

\(1\leq{N}\leq{1000}\)

\(1\leq{K}\leq{4\cdot{10^{7}}}\)

\(1\leq{w}\leq{10^7}\)

4개의 반이 있고 각 반의 학생수는 N명이며, 각 학생들의 몸무게 w 가 주어진다.

반 마다 한명 씩을 골라서 총 네명의 선수를 선발하는데 네 선수의 몸무게의 합이 K와 가장 근접하도록

선수들을 선발하여 그 몸무게의 합을 구하는 문제이다. 만약 답이 여러개라면 그중 작은 값을 답으로한다.

우선 가장 무식하게 푸는 방법이 완전탐색을 하는 방법이며 O(N^4) 이 걸린다. N이 최대 1000이기 때문에

무리가 있다. 그런데 조금만 생각을 해보면 세 개의 반에서 선수가 골라졌다면 남은 한 반에서는

K와 가장 가까운 학생을 고르면 되기 때문에 K-(세 반에서 뽑은 학생들의 몸무게의 합) 으로 이분탐색을 하면 된다.

하지만 그래도 O(N^3lgN) 의 시간 복잡도이기 때문에 너무 느리다.

일단 N이 세제곱되면 안된다.. 제곱은 되는데, 이럴 때 쓸 수 있는 아주 좋은 방법이 둘로 나누어 모든경우를 고려한뒤

둘을 합치는 방법이다. 두반만 고려하는 데에는 N^2 의 시간이 걸리기 때문에 두반씩 쪼개서 각각에 대해

모든 경우를 고려하는건 O(N^2)의 시간에 가능하다.

그렇다면 각각 둘을 어떻게 합칠까?

1반과 2반의 모든 학생들에 대해 각 반별로 한명씩 골라서 몸무게의 합을 구하는 방법은 ON^2) 가지 이다.

그러면 1반과 2반에서 한명씩 골라 몸무게를 합한것이 A라고 할 때,

나머지 두 반에서 고른 학생들의 몸무게의 합이 K-A 에 가장 가깝게 하면되는 것이다.

그럼 또 3반과 4반에서 각각 한명씩 골라 몸무게를 합친 값은 O(N^2)개가 있다.

그럼 이걸 정렬하고 K-A로 lower_bound 하면 O(N^2lgN) 에 답을 구할 수가 있다.

lower_bound 를 했을 때 나오는 위치를 pos 라고 했을 때

pos의 원소와 pos-1 번째 원소만 봐주면 되는데, 그 이유는 pos 번째놈은 K-A 이상의 수 일 것이다.

그러면 A와의 합은 K이상일텐데 그럼 pos+1 부터는 A와의 합이 K이상이기 때문에

A와 pos번째 놈의 합 이상이면서 K이상이기 때문에 pos보다 최적의 답이 될 수 없다.

그렇지만 pos-1은 더 최적의 답이 될 수 있기 때문에 봐줘야한다.

lower_bound 는 같은 원소가 여러개 있을 때 그 중 가장 첫번째 원소의 위치를 찾기 때문에

중복제거를 할 필요가 없이 pos와 pos-1만 보면 되는 것이다. 다른 문제였다면 중복제거를 해줄 필요가 있을 가능성이 있다.

그리고 사실 처음에는 중복제거를 꼭 해야하는줄 알고, 그리고 구현을 간단하게 하기 위해 set을 썼는데

시간복잡도가 같은데도 불구하고 3초안에 안돌아서 TLE가 났다.. 원인은 잘 모르겠다. 테케가 여러개라서 그렇다고하는데

아무리 그래도그렇지.. 원래 set이 좀 많이 느린가보다.

#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9+7;
const int INF = 0x3c3c3c3c;
const long long INFL = 0x3c3c3c3c3c3c3c3c;
 
int N, T;
vector<long long> g[2];
long long K;
long long A[4][1003];
int main() {
    scanf("%d",&T);
    while(T--){
        g[0].clear();
        g[1].clear();
 
        scanf("%lld%d", &K, &N);
        for(int i = 0 ; i < 4; i++){
            for(int j = 0 ; j < N; j++){
                scanf("%lld",&A[i][j]);
            }
        }
        for(int k = 0 ; k < 2; k++){
            for(int i = 0 ; i < N; i++){
                for(int j = 0; j < N; j++){
                    long long sum = A[2*k][i] + A[2*k + 1][j];
                    g[k].push_back(sum);
                }
            }
        }
 
        for(int i = 0 ; i < 2; i++) sort(g[i].begin(), g[i].end());
 
        long long ans = INFL;
        for(long long u1 : g[0]){
            auto it2 = lower_bound(g[1].begin(), g[1].end(), K - u1);
            if(it2 != g[1].end()) {
                long long sum = u1 + (*it2);
                if(abs(ans - K) > abs(sum - K)) ans = sum;
                if(abs(ans - K) == abs(sum - K) && ans > sum) ans = sum;
            }
            if(it2 != g[1].begin()) {
                it2--;
                long long sum = u1 + (*it2);
                if(abs(ans - K) > abs(sum - K)) ans = sum;
                if(abs(ans - K) == abs(sum - K) && ans > sum) ans = sum;
            }
        }
        printf("%lld\n", ans);
    }
 
    return 0;
}