백준 2467-c++

용액
이번문제는 일단 투포인터를 이용해야한다.
문제를 다 풀고 투포인터를 사용해야합니다~ 이건 도움이 아에 안되고, 우선 왜? 투포인터를 사용해야할까?

-99 -3 -2 1 100 이렇게 용액이 주어진다면, 완전탐색으로는 -99 -3, -99 -2, -99 1, -99 100 이렇게 확인을하고
나머지것들도 동일하게 확인을 하면 될것이다.
그렇게하면 최소한 이중 포문을 써야하는데, 이렇게 되면
O(n^2)이 되고 n값이 100000개니까 n^2이면 무조건 시간초과가 날것이다.

사실 두용액이라는 문제를 미리 풀어봐서 이 문제를 쉽게 풀었는데,
힌트는 문제안에 있었다.

1. 0과 가깝게 만든다.
2. 오름차순으로 주어진다.

보면, 가장 큰 수와 가장 작은수를 더해보자 1이다.
2번째 조건을 확인하면 오름차순으로 주어지므로, 0과 가깝게 만들기 위해서 현재 100보다 적게 더해야 할것이다.
그래서 100이전인 1로 이동한다.
이렇게 되면 -99와 1을 더하게 되는데 -98이다. 0보다 작으므로 0과 가깝게 하려면 덜 빼야한다. 그러므로 -99에서 한칸 옴겨서 -3을 확인한다.

즉 이러한 로직을 수행하려면, 0과 가까워지기위해서 덜 더하거나, 덜 빼야한다.
만약 예시로 -99 -2 -3 1 4 5 이렇게되어있다고 가정하면, -2에서 오른쪽으로 간다는 뜻은 덜빼겠다는것이다. 왜냐하면 현재 합이 음수니까, -2 1=>-1 이고
만약에 -2에서 오른쪽이 -1이라면 -1만큼 덜빼는거니까 옴겨주면 -1+1=0이 될것이다. 그런데 -3으로 더 커버리면 옴겨줬는데 -가중치가 더 커지게된다.

고로 이문제는 투포인터를 쓰는데 정렬이 되어있는것이 핵심이다.

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

int main() {
	int n = 0;
	cin >> n;
	vector<long long int>v;
	for (int i = 0; i < n; i++) {
		long long int t = 0;
		cin >> t;
		v.push_back(t);
	}
	int start = 0;
	int end = v.size() - 1;
	long long int minimum = 2000000000;
	long long int ra, rb;
	while (start < end) {
		int t = v[start] + v[end];
		if (minimum > abs(t)) {
			minimum = abs(t);
			ra = v[start];
			rb = v[end];
		}
		if (t == 0) break;
		else if (t < 0) start++;
		else end--;
	}
	cout << ra << "\n";
	cout << rb << "\n";
}