[BOJ/백준][Gold4] 2473 : 세 용액 (C++)

www.acmicpc.net/problem/2473

2473번: 세 용액

 

 

[난이도] Gold4

[유형] 이분탐색

 

[풀이]

a+b+C의 절댓값이 0에 가장 가까운 a,b,c를 찾는 문제
N이 5000이므로 N^3으로 풀수가 없다. => 이분탐색 이용
a,b를 결정하고 (N^2) 그 a,b일 때 가장 최적의 c를 이분탐색으로
찾는다(lgN).
s=a+b 일때 0~N-1중 -s의 lower_bound를 찾는다. lower_bound의 위치가
idx이고 a[idx] != -s인 경우에는 idx-1이 최적일수도 있다.
또한 a[idx] == s이어도 idx가 a또는 b인 경우에는 최적이 될 수 없다.
그러므로 넉넉하게 idx-5 ~ idx+5까지 체크하면서 a,b가 아니면서 절댓값이
최소가 되는 c를 찾아야 한다.

#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;
using ll = long long;
int N,a[5000],r[3];
ll mxN = 9e10;
int main(){
    scanf("%d",&N);
    for(int i=0;i<N;i++) scanf("%d",&a[i]);
    sort(a,a+N);

    for(int i=0;i<N-1;i++){
        for(int j=i+1;j<N;j++){
            ll s = a[i]+a[j];
            int idx = lower_bound(a,a+N,-s)-a;
            for(int k=idx-5;k<idx+5;k++){
                if(k<0||k>=N||k==i||k==j) continue;
                ll ss = abs(s+a[k]);
                if(ss < mxN){
                    mxN = ss;
                    r[0]=i,r[1]=j,r[2]=k;
                }
            }
        }
    }
    sort(r,r+3);
    for(int i=0;i<3;i++) printf("%d ",a[r[i]]);
}

 

github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold4/2473.cpp