[2473] 세 용액

문제: https://www.acmicpc.net/problem/2473

KOI 고등부 문제이다.

주어진 배열에서 세 숫자를 더했을 때

0과 가장 가까운 숫자들을 출력하는 문제이다.

처음엔 단순하게 생각해서

정렬된 배열 arr에서

arr[i] + arr[j] = k 라고 했을 때 

lower_bound로 i+1 ~ j-1 구간에서 -k와 가장 가까운 수를 찾아

i, j, -k와 가장 가까운 수의 합으로

최소값을 갱신해 갈려고 했다.

하지만 계산해보면 O(N^2 * lg N) 이므로 5000*5000*12 = 3억이 나온다.

즉, 시간 초과다.

다른 방법을 찾다가 O(N^2)에 해결하는 방법을 찾아서 소개한다.

3-SUM이라는 알고리즘이다.

출처 위키: 3SUM

영어는 잘 모르겠고

간단하게 정렬된 배열 arr가 있고

arr[i] + arr[j] + arr[k] = x 라고 했을 때 (i<j<k)

그 중 하나를(i) 고정시키고 (i = 0 to n-2) O(N)

나머지 j와 k를 투 포인트 처럼 각각을 한 칸씩 이동시키면서 (j= i+1 to k-1, k = n-1 to j+1) O(N)

원하는 값을 찾는 알고리즘이다. 

오름차순 정렬에 O(N * lg N)을 사용했다고 해도

O(N^2)의 시간복잡도를 가지게 된다.

말로만 하면 좀 어려워서 위의 위키 사이트에 들어가면 있는 예제를 가지고 왔다.

 -10 -7 -3 2 4 8 10  (a+b+c==-7)
 -10 -7 -3 2 4 8 10  (a+b+c==-3)
 -10 -7 -3 2 4 8 10  (a+b+c==2)
 -10 -7 -3 2 4 8 10  (a+b+c==0)

초록 색으로 되어있는 값이 고정시키는 값이고 파란 색 값들이 변경되는 값이다.

arr[i] = -10 라고 했을 때

arr[j]는 -7, arr[k]는 10으로 시작한다.

잠시 목표를 리마인드 하자면

우리가 찾는 것은 세 숫자의 합이 0과 가까운 수를 찾는 것이다.

arr[i] + arr[j] + arr[k] = -7이다.

그렇다면 0과 가까워질려면 j++와 k--중 무엇을 해야 더 가까워질까?

배열이 정렬되어 있다는 것을 알고 있다면

현재 세 수의 합이 목표 값(0) 보다 작으므로

j와 k중 작은 숫자인 j를 하나 올려주면 된다.

계속 진행하다보면

arr[i] = -10, arr[j]=2, arr[k] =10 일 경우 세 수의 합은 2이다.

목표 값(0)보다 크므로

가장 큰 숫자인 k를 하나 낮춰서

우리가 원하는 값에 근접시켜가는 것이다.

이런 식으로 한 고정된 숫자에 대해 비교를 N-i-1번만 하면 되므로 (j >= k 가 되는 순간 종료)

시간복잡도는 O(N^2)이 되는 것이다.

또한, 이 문제는 범위가 까다롭다. 

입력 범위가 10^-9 ~ 10^9 이라 덧셈 하다보면 int로는 오버플로우가 난다. (int는 대략 -20억 ~ 20억 정도 라고 생각하면 된다.)

long long을 사용해 주도록 하자.

그리고 최소 값을 갱신할 때 그냥 min함수를 써버리면 0에 가장 가까운 수가 아닌 

가장 작은 음수 값으로 갱신되므로

절대 값으로 비교를 해주면 된다.

끝.

#include<cstdio>
#include<algorithm>
using namespace std;
long long arr[5050], ans[3];
int main(){
    int n;
    scanf("%d", &n);
    for(int i=0; i<n; i++){
        scanf("%lld", arr+i);
    }
    sort(arr, arr+n);
    long long mini = 3*10e9+10;
    for(int i=0; i<n-2; i++){
        int j, k;
        j = i+1; k = n-1;
        while(1){
            if(j>=k) break;
            long long x = arr[i]+arr[j]+arr[k];
            long long nx = x<0?-x:x;
            if(mini > nx){
                mini = nx;
                ans[0]=arr[i];
                ans[1]=arr[j];
                ans[2]=arr[k];
            }
            if(x>0){
                k--;
            }else{
                j++;
            }
        }
    }
    for(int i=0; i<3; i++){
        printf("%lld ", ans[i]);
    }
    return 0;
}