[C++] BAEKJOON 9007번 카누선수(ACM-ICPC 예선 Daejeon 2012

문제보기

9007번: 카누 선수

쉽게 생각해서 4중 for 문으로 구현하면 쉽게 나올 수 있지만 시간초과에 걸립니다. n의 범위가 최대 10^3 까지 이고 4중 for 문이면 10^12 이고 1초 이상이므로 여러 테스트 케이스가 들어왔을 때, 3초안에 해결을 할 수가 없습니다. 그렇다면 어떤 방법을 사용해야 할까요?

다음과 같은 알고리즘으로 해결하였습니다.

1. 두 개의 반 씩 짝을 지어서 o(n^2) 으로 나올 수 있는 합에 대한 새로운 배열 생성
2. 새로 생긴 두 배열 정렬
3. 이분 탐색을 이용하여 가장 근사한 값 찾기

 

이에 대한 코드 전문입니다.

#include <iostream>
#include <algorithm>

using namespace std;

// 절대값 구하는 함수
int abs(int num){
    if (num<0) num = -num;
    return num;
}

int main(int argc, const char * argv[]) {

    int T;
    cin >> T;
    
    for (int t=0;t<T;t++){
        int table[4][1000];
        int goal,numInCanoe;
        cin >> goal >> numInCanoe;
        
        for (int i=0;i<4;i++){
            for (int j=0;j<numInCanoe;j++){
                cin >> table[i][j];
            }
        }
        
        int list1[1000000];
        int list2[1000000];
        
        for (int i=0;i<numInCanoe;i++){
            for (int j=0;j<numInCanoe;j++){
                list1[i*numInCanoe+j] = table[0][i] + table[1][j];
                list2[i*numInCanoe+j] = table[2][i] + table[3][j];
            }
        }
        
        int length = numInCanoe*numInCanoe;
        
        sort(list1, list1+ length);
        sort(list2, list2+ length);
        
        int minValue = 999999999;
        int result = 0;
        int flag = 0;
        for (int i=0;i<length;i++){
            int goal2 = goal - list1[i];
            
            int left=0,right=length-1;
            while (left<=right){
                int point = (left+ right) / 2;
                
                // 목표치에 대한 편차가 같으면 작은 값을 택한다.
                if(minValue == abs(goal2 - list2[point]) && result > list1[i] + list2[point]) {
                    result = list1[i] + list2[point];
                }
                else if (minValue > abs(goal2 - list2[point])){
                    minValue = abs(goal2 - list2[point]);
                    result = list1[i] + list2[point];
                }
                
                if (goal2 < list2[point]){
                    right = point-1;
                }
                else if (goal2 > list2[point]){
                    left = point+1;
                }
                else {
                    cout << goal << endl;
                    flag = 1;
                    break;
                }
                
            }
            if (flag) break;
        }
        
        if (!flag){
            cout << result << endl;
        }
    }
    return 0;
}