BOJ 2467 용액

www.acmicpc.net/problem/2467

2467번: 용액

 

처음 생각한 방법은 모든 숫자쌍을 비교하는 것이였다. 

하지만, 시간복잡도가 O(n^2) 였기 때문에 해당 문제를 시간 내에 푸는 것은 불가능 했다.

 

 

문제를 보면서 곰곰히 생각해보니, 두 숫자의 합의 절대값이 작은 경우들만 추려서 확인하면 될 것 같다는 생각이 들었다.

그렇게 하기 위해서는 배열을 정렬한 뒤, 양 끝에서부터 중앙으로 다가오는 포인터를 두어  포인터가 가리키는 두 정수의 절대값을 비교하면서 인덱스를 조절해나가면 필요한 비교만 진행할 수 있다고 생각했다.

 

마침 문제에서도 배열이 정렬되어 있어서 해당 방법을 사용하기로 했다.

 

아래는 처음 제출한 코드이다.

#include <cstdio>
#include <algorithm>

int main(){
    int n;
    int arr[100000];
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        scanf("%d",arr+i);
    }
    
    if(arr[0] >= 0 && arr[1] >= 0){
        printf("%d %d\n",arr[0],arr[1]);
    }
    else if(arr[n-1]<= 0&& arr[n-2] <= 0){
        printf("%d %d\n",arr[n-2],arr[n-1]);
    }
    else{
        int i = 0, j = n-1;
        int sum = std::abs(arr[0] + arr[n-1]);
        int answer1 = arr[0], answer2 = arr[n-1];

        while(true){

            if( std::abs(arr[i] + arr[j]) < sum ){
                answer1 = arr[i];
                answer2 = arr[j];
                sum = std::abs(arr[i]+ arr[j]);
            }


            if(arr[i]+arr[j] == 0){
                break;
            }
            else if(std::abs(arr[i]) > std::abs(arr[j]) &&
                i+1 < n && arr[i+1] < 0){
                i++;
            }
            else if(std::abs(arr[i]) < std::abs(arr[j]) &&
                j-1 >= 0 && arr[j-1] > 0 ){
                j--;
            }
            else{
            
                break;
            }
        }
        printf("%d %d\n",answer1, answer2);
    }


    return 0;
}

 

하지만, 해당 코드로는 정답을 받지 못했다.

 

맞왜틀을 외치면서 생각 끝에 반례를 찾아낼 수 있었다.

[-10000, 1, 2]

 

정답인 경우는 반드시 [음수, 양수] 일 거라는 고정관념에서 비롯된 문제였다.

 

해당 부분을 수정하여 제출하였고, 정답을 받을 수 있었다.

 

아래는 정답 코드이다.

#include <cstdio>
#include <algorithm>

int main(){
    int n;
    int arr[100000];
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        scanf("%d",arr+i);
    }
    
    if(arr[0] >= 0 && arr[1] >= 0){
        printf("%d %d\n",arr[0],arr[1]);
    }
    else if(arr[n-1]<= 0&& arr[n-2] <= 0){
        printf("%d %d\n",arr[n-2],arr[n-1]);
    }
    else{
        int i = 0, j = n-1;
        int sum = std::abs(arr[0] + arr[n-1]);
        int answer1 = arr[0], answer2 = arr[n-1];

        while(i<j){

            if( std::abs(arr[i] + arr[j]) < sum ){
                answer1 = arr[i];
                answer2 = arr[j];
                sum = std::abs(arr[i]+ arr[j]);
            }


            if(arr[i]+arr[j] == 0){
                break;
            }
            else if(std::abs(arr[i]) > std::abs(arr[j])){
                i++;
            }
            else if(std::abs(arr[i]) < std::abs(arr[j])){
                j--;
            }
        }
        printf("%d %d\n",answer1, answer2);
    }


    return 0;
}