[BOJ 2473] 세 용액 - JAVA, Gold3

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

2473번: 세 용액

풀이

 

사용한 알고리즘 : 이분 탐색

 

풀이전략

 

두 용액에서와 달리 이번 문제는 세 용액의 합이 0에 가까워야 한다.

 

저번 두 용액에서는 입력받은 용액들을 오름차순으로 정렬시키고,

최좌측 인덱스 start와 최우측 인덱스 end에 속하는 양 끝값의 합을 구하고

이 합이 0보다 크면 총합의 값을 줄이기위해 end=end-1,

합이 0보다 작으면 총합의 값을 늘리기 위해 start=start+1,

합이 0이면 더 이상 총합의 합이 작아질 수 없기때문에 반복문을 탈출시켰다.

 

그리고 총합이 가장 작았을 때의 각각의 값을 출력했었다.

 

세 용액도 비슷한 매커니즘을 가진다.

단, start와 end를 총합에 따라 변화시키지 않는다.

 

아래 그림을 보고 설명하자면

start는 항상 end보다 더 작은 인덱스를 가진 상태면서

그 둘 사이에 값이 하나라도 있는 start와 end의 모든 경우를 탐색해야한다.

 

그리고 start와 end 사이의 리스트 범위에서 

list[start] + list[end] + list[x]가 최소값이 될 수 있는 x를 이분 탐색을 통해 찾아내면 된다.

 

이 때 x를 찾기 위해 주어지는 이분 탐색의

시작점은 start+1, 끝점은 end-1이다.

이유는 start와 end 지점의 값이 list[x]로 나오지 않도록 하기 위해서다.

 

 

제출코드

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main{
    static long list[];
    static long minVal = (long)2e12;

    static long smallVal;
    static long middleVal;
    static long bigVal;

    static void binarySearch(int start, int end){
        int front=start+1;
        int rear=end-1;
        while(front<=rear){
            int mid = (front+rear)/2;

            if(Math.abs(list[start]+list[end]+list[mid])<minVal){
                minVal=Math.abs(list[start]+list[end]+list[mid]);
                smallVal=list[start];
                middleVal=list[mid];
                bigVal=list[end];
            }

            if(list[start]+list[end]+list[mid]==0) break;
            else if(list[start]+list[end]+list[mid]<0) front=mid+1;
            else rear=mid-1;
        }
    }

    static void func(int start, int end){
        for(int i=start;i<end-1;++i){
            for(int j=end;j>i+1;--j){
                binarySearch(i,j);
            }
        }
    }

    public static void main(String args[]) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        int N = Integer.parseInt(br.readLine());
        list = new long[N];

        st = new StringTokenizer(br.readLine());
        for(int i=0;i<N;++i){
            list[i]=Long.parseLong(st.nextToken());
        }
        Arrays.sort(list);

        func(0,N-1);

        bw.write(smallVal+" "+middleVal+" "+bigVal);
        bw.flush();
        bw.close();
    }
}