[백준 9007] 카누 선수 (C++)

문제 링크: https://www.acmicpc.net/problem/9007

9007번: 카누 선수

1. 주의할 점

- 시간복잡도를 줄이려고 노력한다

- TestCase를 시작하기 전, 연산에 사용되는 모든 벡터 및 값을 초기화한다

 

2. 구현

- 4개의 집합(V[])을 2개씩 묶어서 각 집합의 모든 원소의 합을 twoSum[]에 저장한다

- 두 집합의 합을 구할때: O(N^2)

- twoSum을 통해 Weight과 비교할 때(twoSum[0]의 길이를 A(=N^2)라고 할 때): O(AlgA)

- 이분탐색을 이용해서 해결한다

- twoSum[] 배열중에서 1개의 배열만 오름차순으로 정렬한다(시간복잡도: O(AlgA))

- Result의 값을 각 배열 첫번째 원소의 합으로 초기화한다

- twoSum[0]의 모든 원소에 대해 twoSum[1]의 원소와 비교를 한다. 이때, 이분탐색을 통해 twoSum[1]을 탐색할 때의 시간복잡도를 A에서 lgA로 줄인다

- 각 조건에 맞게 Result를 갱신하며, L과 R의 값을 수정한다

#include <iostream>
#include <set>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int test,weight,num,val;
    cin >> test;
    while(test--){
        cin>>weight>>num;
        vector<int> v[4];
        for(int i=0;i<4;i++){
            for(int j=0;j<num;j++){
                cin>>val;
                v[i].push_back(val);
            }
        }
        vector<int> twoSum[2];
        for(int i=0;i<2;i++)
            for(int j=0;j<num;j++)
                for(int k=0;k<num;k++)
                    twoSum[i].push_back(v[i*2][j]+v[i*2+1][k]);
        sort(twoSum[1].begin(),twoSum[1].end());
        
        int result = twoSum[0][0]+twoSum[1][0];
        bool finish = false;
        for(int i=0;i<num*num;i++){
            int l=0,r=num*num-1,mid,firVal = twoSum[0][i];
            while(l<=r){
                mid = l +(r-l)/2;
                int sum = firVal+twoSum[1][mid];
                if(abs(result-weight)>abs(weight-sum))   result = sum;
                else if(abs(result-weight)==abs(weight-sum)) result = min(result,sum);
                if(sum<weight)  l = mid+1;    //sum을 늘린다
                else if(sum>weight) r = mid-1;        //sum을 줄인다
                else{       //정확히 sum
                    finish=true;
                    break;
                }
            }
            if(finish) break;
        }
        cout<<result<<'\n';
    }
    return 0;
}