[백준] 2470 두 용액

1. 문제

www.acmicpc.net/problem/2470

2470번: 두 용액

2. 접근방법

합이 0에 가깝게 만드는 두 수를 찾는 문제

 

합을 0에 가깝게 어떻게 만들까?

 

여기서 생각해보면

배열 안의 값중 합이 0에 가장 가깝게 만드는 경우는

두 수가 절대값으로 정렬했을 때 붙어있어야만 가능하다.

 

위 예제에서도 절대 값 정렬을 하면

-99 98 4 -2 -1

 

정답은 합이 -1인 -99와 98

 

뭔가 반례가 있지 않을까 싶어

다양한 경우를 생각해봤지만 반례를 찾지 못해

이대로 풀이를 해보니 맞았습니다를 받았다.

 

증명은 어떻게 해야할지 감이 잘안와서

지나가는 수학과님이 보신다면 증명 좀 해주면 감사하겠슴니다.

 

어쨌든 절대값으로 정렬하고

정렬된 배열에서 앞뒤 숫자 합을 구해

최소값이 나오게 하는 두 수를 구하면 된다.

3. 자바 코드

package Gold;

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

public class G1_2470두용액 {
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(br.readLine());
		StringTokenizer st = new StringTokenizer(br.readLine());
		Integer [] arr = new Integer [N];
		for(int i = 0 ; i < N ; i++)
			arr[i] = Integer.parseInt(st.nextToken());
		Arrays.parallelSort(arr, new Comparator<Integer>() {
			@Override
			public int compare(Integer o1, Integer o2) {
				return Math.abs(o1)-Math.abs(o2);
			}
		});
		int min = Integer.MAX_VALUE;
		int x = 0;
		int y = 0;
		for(int i = 0 ; i < N-1; i++) {
			if(Math.abs(Integer.sum(arr[i], arr[i+1])) < min) {
				x = arr[i];
				y = arr[i+1];
				min = Math.abs(x+y);
			}
		}
		if(x > y)
			x = y ^ x ^(y=x);
		System.out.println(x+" "+y);
		
	}

}

4. 마치며

뭔가 반례가 있을 것 같은데 안나와서 더 당황..