[BOJ] 2467용액

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

2467번: 용액

1. 모든 조합을 모두 살펴보는 것은 nC2만큼의 계산이 필요하다. n이 최대 10만이므로 시간초과가 날 것이다.

2. 답이 될 후보들 추리기

힌트로 오름차순으로 숫자를 주기 때문에, 이분탐색(lower_bound)으로 어떤 숫자 n의 -n과 같거나 큰 숫자를 구하고, 이 숫자의 왼쪽에 있는 숫자, 이 두 개를 비교해서 답을 구하면 될 것이라고 생각했다. 그런데, 이 경우에는 모든 숫자들이 0포함 양수거나 음수일 때의 경우를 따로 고려해야 한다.

다른 방법은 투 포인터로 풀 수 있는데 처음에 생각나지 않아서 다른 사람 코드를 살펴보았다!

 

투포인터 코드

#include <iostream>
#include <algorithm>
using namespace std;
int n;
int A[100010];
int a,b;
int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    /* initialize & recieve inputs */ 
    int tmp = 2000000001;
    cin>>n;
    for(int i = 0; i < n; i++) cin>>A[i];
    /*set two-pointers */
    int s = 0, e = n-1, a, b;
    
    while(s < e){
        if(abs(A[s] + A[e]) < tmp) {
            tmp =abs(A[s] + A[e]);
            a = A[s], b = A[e];
            if(A[s] + A[e] == 0)break;
        }
        if(A[s] + A[e] < 0) s++;
        else e--;
    }
    cout<<a<<" "<<b;
    return 0;
}

이분탐색 코드

#include <iostream>
#include <algorithm>
using namespace std;
int n;
int A[100010];
int a,b;
int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int tmp = 2000000001;
    cin>>n;
    for(int i = 0; i < n; i++) cin>>A[i];
    /*다 음수이거나 양수일 때*/
    if(A[n-1] < 0) return cout<<A[n-2] <<" "<<A[n-1],0;
    if(A[0] >= 0) return cout<<A[0] << " "<<A[1], 0;
    /* 섞여 있을 때 이분 탐색하기 */
    for(int i = 0; A[i] < 0; i++){
        auto it = lower_bound(A,A+n,-A[i]);
        if(A[i] != *(it-1) && abs(A[i] + *(it-1)) < tmp) {
            tmp =  abs(A[i] + *(it-1));
            a = A[i];
            b = *(it-1);
        }
        if(abs(A[i] + *it) < tmp) {
            tmp =  abs(*it + A[i]);
            a = A[i];
            b = *it;
        }
    }
    cout<<a<<" "<<b;
    return 0;
}