BOJ 2473: 세 용액

#BOJ 2473: 세 용액

2473번: 세 용액

#풀이

지난 번에 풀었던 용액과 거의 비슷한 문제이다. 세 용액을 골라서 합이 가장 0에 가까운 수를 오름차순으로 출력하는 문제이다.

 

용액 문제에서와 마찬가지로 lower_bound를 사용해서 해결할 수 있다.

 

if 문 안에서 3개를 다 더하면 int 형의 범위를 넘어가므로 long long 으로 캐스팅을 하든가 처음부터 long long 으로 받아야 한다.

 

abs(arr1[i] + arr1[j] + arr1[low + 1])

이 부분에서 오버플로우가 날 수 있다.

arr1의 형태가 int 형이라면 1,000,000,000 을 3번 더하면 int 범위를 넘어간다.

#코드

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int n;
vector<long long> arr1;
long long ans1 = 1e+9 + 1;
long long ans2 = 1e+9 + 1;
long long ans3 = 1e+9 + 1;// 지수표기법은 붙어야 에러가 안난다.
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	for (int i = 0; i < n; i++) {
		int num;
		cin >> num;
		arr1.push_back(num);
	}
	sort(arr1.begin(), arr1.end());
	
	for (int i = 0; i < n - 1; i++) {
		for (int j = i + 1; j < n; j++) {
			int low = lower_bound(arr1.begin(), arr1.end(), -1 * (arr1[i] + arr1[j]))
				-arr1.begin();
			if (low + 1 < n && i != low + 1 && j != low+1 && abs(arr1[i] + arr1[j] + arr1[low + 1]) < abs(ans1 + ans2 + ans3)) {
				ans1 = arr1[i];
				ans2 = arr1[j];
				ans3 = arr1[low+1];
				
			}
			if (low < n && i != low && j != low && abs(arr1[i] + arr1[j] + arr1[low]) < abs(ans1 + ans2 + ans3)) {
				ans1 = arr1[i];
				ans2 = arr1[j];
				ans3 = arr1[low];
			}
			if (low - 1 >= 0 && i != low -1 && j != low -1 && abs(arr1[i] + arr1[j] + arr1[low -1]) < abs(ans1 + ans2 + ans3)) {
				ans1 = arr1[i];
				ans2 = arr1[j];
				ans3 = arr1[low - 1];
			}

		}
	}
	vector<long long > v;
	v.push_back(ans1);
	v.push_back(ans2);
	v.push_back(ans3);
	sort(v.begin(), v.end());
	for (int i = 0; i < 3; i++)
		cout << v[i] << ' ';
	cout << '\n';

	return 0;
}