[백준 2467번] 용액 (java)

 

2467번: 용액

이분탐색으로 풀었다.

 

위의 예제에서 -99 -2 -1 4 98 이 주어질 때,

 

-99와 더해서 0이 되려면 99라는 수가 필요하다. 그러면 -99 보다 오른쪽에 있는 -2 1 4 98 중에서 이분탐색을 이용하여 99와 가장 가까운 수를 찾아서 -99와 더한다.  -> -99 + 98 = -1

 

그 다음, -2와 더해서 0이 되려면 2라는 수가 필요하다. -2보다 오른쪽에 있는 1 4 98 중에서 이분탐색을 통해 2와 가장 가까운 수를 찾아서 -2와 더한다. -> -2 + 4 = 2

 

-1과 더해서 0이 되려면 1이라는 수가 필요하다. 1보다 오른쪽에 있는 4 98 중에서 이분탐색을 통해

1과 가장 가까운 수를 찾아서 -1과 더한다. -> -1 + 4 = 3

 

-1, 2, 3 중에서 0과 가장 가까운 값은 -1이다.

그러므로 두 용액은 -99, 98이 된다.

 

 

소스코드 : 

	import java.io.*;
	import java.util.Arrays;
	public class n02467 {
	static int N;
	static long[] arr;
	static long min = Long.MAX_VALUE;
	static int a, b;
	public static void main(String[] args) throws Exception {
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	N = Integer.parseInt(br.readLine());
	arr = new long[N];
	String[] sarr = br.readLine().split(" ");
	for (int i = 0; i < N; i++)
	arr[i] = Integer.parseInt(sarr[i]);
	Arrays.sort(arr);
	for (int i = 0; i < N - 1; i++) {
	int idx = binSearch((int) (-arr[i]), i + 1, N - 1);
	long sum = Math.abs(arr[i] + arr[idx]);
	if (min > sum) {
	a = (int) arr[i];
	b = (int) arr[idx];
	min = sum;
	}
	}
	bw.write(a + " " + b + "\n");
	bw.flush();
	}
	public static int binSearch(int n, int left, int right) {
	int pl = left;
	int pr = right;
	do {
	int pc = (pl + pr) / 2;
	if (arr[pc] == n)
	return pc;
	if (arr[pc] < n)
	pl = pc + 1;
	else
	pr = pc - 1;
	} while (pl <= pr);
	if (pl > right)
	return pr;
	if (pr < left)
	return pl;
	if (Math.abs(n - arr[pl]) < Math.abs(n - arr[pr]))
	return pl;
	else
	return pr;
	}
	}

view raw 2467.java hosted with ❤ by GitHub