[백준 / C++] 2467번: 용액 (이분탐색 X, 투포인터 X, 조금 다른 풀이)

 

 

 

 

 

https://www.acmicpc.net/problem/2467

2467번: 용액

난이도: solved.ac 골드 5

 

접근 방법

서로 다른 두 수의 합이 0과 가장 가까운 것을 찾아야 하는 문제다.

 

합이 0과 가장 가까우려면 어떤 특징이 있을지에 대해 생각해 보았다.

 

합이 0과 가까우면, 두 수의 절댓값이 서로 비슷하다는 특징이 있다는 것을 발견했다.

 

이의 역은 성립하지 않는데, 절대값이 비슷하다고 합이 0과 가까운 것은 아니다.

 

하지만 합이 0과 가까운 두 수는 절대값이 서로 비슷하므로, 문제에서 주어진 수열에 절댓값을 씌운 것을 기준으로 오름차순 정렬해 나열했다.

 

그리고 맨 앞 원소부터 시작해 바로 뒤에 이어지는 수와의 합을 계산해 합이 가장 가까운 것을 고르도록 했다.

 

즉, i = 0부터 i = N - 2까지에서 arr[i] + arr[i+1]의 합이 가장 작은 arr[i]와 arr[i+1]를 찾는 것이다.

 

그리고 작은 수부터 출력하도록 했으므로 두 수를 정렬해 출력하면 된다.

 

이 풀이가 가능한 이유는 두 수의 합이 0과 가까우면 절대값이 서로 비슷하고, 절대값 씌운 것을 기준으로 정렬시키면 인접한 두 수의 절대값 차이는 무조건 최소가 되기 때문이다.

 

코드

#include <bits/stdc++.h>
using namespace std;

int cmp(int a, int b) {
	return abs(a) < abs(b);
}
int Min = 2000000000, sum;
int ans[2];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int N, num, i;
	cin >> N;
	vector<int> arr;
	for (i = 0; i < N; i++) {
		cin >> num;
		arr.push_back(num);
	}
	sort(arr.begin(), arr.end(), cmp);
	for (i = 0; i < N - 1; i++) {
		sum = abs(arr[i] + arr[i + 1]);
		if (sum < Min) {
			Min = sum;
			ans[0] = arr[i];
			ans[1] = arr[i + 1];
		}
	}
	sort(ans, ans + 2);
	cout << ans[0] << ' ' << ans[1];
}

 

성능

코드 제출 결과