[백준 14921] 용액 합성하기 (JAVA)

문제 링크: https://www.acmicpc.net/problem/14921

14921번: 용액 합성하기

1. 주의할 점

- 용액을 합성할 때 항상 사용될 용액 A를 미리 지정해 놓는다

- 이분탐색을 사용한다

 

2. 구현

- 용액 Num개를 입력 받는다

- For문을 통해 용액 A를 Arr[0]~Arr[Num-1]사이에 모든 용액을 사용한다(사실 Num-2까지만 해도 된다)

- 용액 A를 Arr[i]로 골랐다면, Low = i+1, High = num-1을 가리키도록 설정하고 이분탐색을 시작한다 (Low를 i+1로 놓지않고 0부터 놓는다고 하면 경우의 수가 중복되므로 2배의 시간이 소요된다)

- Mid는 Low + (High-Low)/2로 설정하여 혹시 모를 범위 Overflow를 방지한다

- A용액과 Arr[Mid] 용액의 합이 0이라면 Ans에 0을 대입한 후, 이분탐색을 종료한다

- 이외의 경우, 항상 Ans값을 합과 비교하여 갱신이 필요한 경우 갱신하고, 이분탐색을 계속 진행한다

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	static long arr[];

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int num = Integer.parseInt(br.readLine().trim());
		arr = new long[num];
		String str = br.readLine();
		StringTokenizer st = new StringTokenizer(str);
		for (int i = 0; i < num; i++)
			arr[i] = Integer.parseInt(st.nextToken());
		int low, mid, high;
		long ans=arr[0]+arr[1];
		boolean flag=false;
		for (int i = 0; i < num; i++) {
			long f = arr[i];
			low = i + 1;
			high = num - 1;
			while (low <= high) {
				mid = low + (high - low) / 2;
				long v = f+arr[mid];
				if (f + arr[mid] == 0) {
					ans = 0;
					flag = true;
					break;
				}
				if(Math.abs(ans) > Math.abs(v))	ans = v;
				else if(f+arr[mid]<0)	low = mid+1;
				else	high = mid-1;
			}
			if(flag==true) break;
		}
		System.out.println(ans);
	}
}