수학과의 좌충우돌 프로그래밍

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

카테고리 없음

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

ssung.k 2019. 8. 3. 13:59

문제보기

 

9007번: 카누 선수

문제 국제 카누 경주 챔피언십 (International Canoe Sprint Championship : ICSC)가 머지 않아 개막된다. ICSC에서 인증하는 공식 보트는 C1, C2 그리고 C4로 구성되며, "C"는 카누를 그리고 숫자는 노를 젓는 사람의 수를 의미한다. 카누 경주는 잔잔한 물 위의 여러개로 구획된 직선 코스에서 이루어진다. ICSC에서는 국제 경기를 200m, 500m 그리고 1000m로 구분하고 있다. 한국 스포츠 학교(Korea

www.acmicpc.net

쉽게 생각해서 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;
}

 

Comments