[BOJ 9007] 카누 선수

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

입력으로 4개의 줄당 각각 n개의 몸무게가 주어진다. 이 떄 4각 줄 중 한명씩을 뽑아서 k와 가장 가까운 값을 찾는 문제이다. n의 제한이 1000까지 이므로 모든경우를 시뮬레이션 해보면 1000^4 이므로 당연히 TLE가 날 수 밖에 없다. 그래서 '뭐지 dp인가?....' 하고 열심히 생각해보았지만 역시나 dp 테이블 정의가 되지 않아서 패스 ... 그렇게 그렇게 삽질을 하다가 힌트를 얻고 문제를 풀 수 있었다. 

핵심은 binary_search. 4줄 중 각 2줄씩의 합을 각각의 벡터에 저장을 하고, 2개의 백터들을 통해서 이분탐색을 하는 것이다. 이때 주의할점은 차이가 같은 무게들이 있을 경우에는 작은값을 유지해야 한다는 점이다. 이렇게 구현을 하게 되면 최대 1000개의 n에 대해서 각 벡터당 1000*1000 = 백만의 값이 나오고 각 100만개의 쿼리중에서 각 케이스 별로 이분탐색이 이루어 진다면 100만 * log10^7 = 700만의 연산이 이루어지게 되므로 문제를 해결할 수 있다. 

#include <iostream>
#include <cstdio>
#include <vector>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <set>
#include <queue>
#include <stack>
#define MAX_N 100
#define INF 1e8
#define MOD 1000000007
 
typedef long long ll;
 
using namespace std;
 
int t,n,k,arr[5][1111];
 
vector<int> v1;
vector<int> v2;
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> t;
    while(t--){
        int ans = INF;
        int diff = INF;
        v1.clear();
        v2.clear();
        
        cin >> k >> n;
        for(int i=1;i<=4;i++){
            for(int j=1;j<=n;j++){
                cin >>arr[i][j];
            }
        }
        
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                v1.push_back(arr[1][i]+arr[2][j]);
            }
        }
        
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                v2.push_back(arr[3][i]+arr[4][j]);
            }
        }
        
        sort(v1.begin(),v1.end());
        sort(v2.begin(),v2.end());
 
        
        for(int i=0;i<v1.size();i++){
            int val1 = v1[i];
            int left  = 0;
            int right = (n*n)-1;
            int mid;
            
            while(left <= right){
                
                mid = (left+right)/2;
 
                if(abs(k-(val1+v2[mid])) < diff){
                    diff = abs(k-(val1+v2[mid]));
                    ans = val1+v2[mid];
                }else if(abs(k-(val1+v2[mid])) == diff){
                    ans = min(ans,val1+v2[mid]);
                }
                if(val1 + v2[mid] >= k){
                    right = mid-1;
                }else{
                    left = mid+1;
                }
            }
        }
        cout<<ans <<endl;
    }
    return 0;
}