C++) 백준 2470 두 용액

2470번: 두 용액

---

코드

 

#include <algorithm>
#include <iostream>
#include <cstdlib>

using namespace std;

long long p[100001], m[100001];	// p : 양, m : 음
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	long long tmp, gap = 1000000001, x, y;	
	// gap : 0과 가까운 정도를 담는 변수 
	// x,y : 답을 담을 변수
	int n, i = 0, j = 0;
	// i : 양수 갯수, j : 음수 갯수

	cin >> n;
	for (int k = 0; k < n; k++) {
		cin >> tmp;
		if (tmp < 0) m[i++] = -1 * tmp;
		else p[j++] = tmp;
	}
	
	sort(p, p + j);
	sort(m, m + i);

	// 양, 음 중 한쪽만 치우칠 때
	if (!i) {
		cout << p[0] << " " << p[1];
		return 0;
	}
	if (!j) {
		cout << -1 * m[1] << " " << -1 * m[0];
		return 0;
	}

	for (int k = 0; k < j; k++) {
		long long up = upper_bound(m, m + i, p[k]) - m;	// 가장 차이가 적은 수
		long long gap_up;				// 해당 수와의 차이 값

		if (up == i) up--;
		// 상한이 배열 인덱스 초과 시 빼기 1

		if (up > 0 && abs(p[k] - m[up - 1]) < abs(p[k] - m[up]))
			gap_up = abs(p[k] - m[--up]);
		else {
			gap_up = abs(p[k] - m[up]);
		}	// 인덱스-1의 값과도 비교하여 gap 작은 값 선택
			// 배열이 5 10인 상태에서 up이 6이면 배열의 10인 자리로 인덱스를 잡음 - 때문에 앞과도 비교
		if (gap_up < gap) {
			gap = gap_up; x = p[k]; y = m[up] * -1;	// x는 양수, y는 음수
		}
		if (!gap) break;
	}

	// 양수나 음수만으로 0에 가까운 경우
	if (j > 1 && p[0] + p[1] < gap) { gap = p[0] + p[1];  y = p[0]; x = p[1]; }
	if (i > 1 && m[0] + m[1] < gap) { y = -1 * m[1]; x = -1 * m[0]; }

	cout << y << " " << x;
}

 

 

풀이

 

양수 / 음수 각각 배열로 나눈 후 가장 비슷한 수를 이분 탐색으로 찾는다

 

ex)

     입력 : -5  -3  -1  2  4  6

     양수 : 2 4 6       음수 : 1 3 5

 

1. 양수 배열(p)의 수를 기준으로 음수 배열에서 이분 탐색

2. 찾은 값의 차이(gap)를 구하여 0과 가까운 경우의 수를 출력

 

- 필요한 부가 처리

1. 양수만 존재하거나 음수만 존재하는 경우
2. 이분탐색으로 찾은 인덱스의 값이 최적의 경우인지 -1한 인덱스의 값과 비교
3. 양수 혹은 음수 한 쪽의 두 수의 합으로 0에 가장 가까운 경우

처리가 복잡함 다양한 접근법 공부가 필요