[BOJ] 2470번_두 용액_두 포인터 (C++)

[문제]

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

N개 만큼의 용액을 입력받아 그중 두 개의 용액을 혼합하여 특성 값이 0에 가까운 용액을 만들어내는 두 용액을 찾는 문제이다.

[사용 알고리즘]

두 포인터

[풀이 핵심]

• N개의 용액을 입력받아 vector에 저장하고 sort()함수를 통해 오름차순으로 정렬한다. (답인 두 용액을 오름차순으로 출력해야하는 조건이 있기 때문)
• start와 end라는 두 개의 포인터를 두고, start와 end가 가리키는 값을 더 해서 최고로 0과 가까운 값인지 절대값을 이용해서 비교한다. 두 용액의 특성값의 합을 절대값을 취하고 그 값이 min값보다 작을 경우 result_1과 result_2에 두 용액을 저장해준다.
• 용액 특성값의 합이 0보다 작으면 특성 값의 합을 늘려서 0에 가까워져야 하므로 start를 증가시키고, 0보다 크거나 같으면 특성 값의 합을 줄여서 0에 가까워져야 하므로 end를 감소시킨다.
• 위 과정을 start가 end보다 작으면 계속 반복한다. 모든 연산이 끝난 후 result_1과 result_2가 정답이다.

[코드]

//boj2470번_두 용액_두 포인터

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

using namespace std;

int main() {
	int N;
	cin >> N;

	vector<int> v;

	for (int i = 0; i < N; i++) {
		int num;
		cin >> num;
		v.push_back(num);
	}

	sort(v.begin(), v.end());

	int start = 0;
	int end = v.size() - 1;
	int min = 2147483647;

	int result_1 = 0;
	int result_2 = 0;

	while (start < end) {
		if (min > abs(v[start] + v[end])) {
			result_1 = v[start];
			result_2 = v[end];

			min = abs(v[start] + v[end]);
		}

		if (v[start] + v[end] < 0) {
			start++;
		}
		else {
			end--;
		}
	}
	cout << result_1 << " " << result_2;

	return 0;
}