BOJ 2470 두 용액

www.acmicpc.net/problem/2470

2470번: 두 용액

 

양수인 산성 용액과 음수인 알칼리성 용액이 주어지면 0과 가장 가까운 값의 두 구간을 찾는 문제다.

 

• 투 포인터를 활용하기 위해서 배열을 정렬해준다
• 왼쪽 포인터와 오른쪽 포인터 S = 0, E = n - 1로 설정해준다
• vector에 <절댓값, 구간 2개> 로 입력받고
• 두 구간의 합이 양수면 오른쪽을 줄이고
• 음수면 왼쪽을 줄인다
• 두 포인터가 서로 교차하면 종료

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int ar[100001], n, s, e;
vector<pair<int, pair<int, int>>> ans; 

int main() {
	ios::sync_with_stdio(false); cin.tie(0);

	cin >> n;
	for (int i = 0; i < n; i++) cin >> ar[i];
	sort(ar, ar + n);

	s = 0, e = n - 1; 
	while (s < e) { 
		ans.push_back({ abs(ar[s] + ar[e]),{ar[s],ar[e]} });
		if (ar[s] + ar[e] > 0) e--;
		else s++;
	}
	sort(ans.begin(), ans.end()); 

	cout << ans[0].second.first << ' ' << ans[0].second.second << endl;

	return 0;
}

 

처음엔 s<=e 로 설정해서 계속 틀렸다.

이분 탐색류는 경곗값 범위 설정을 조심히 다뤄야 하는 걸 다시 느낀다.