[투포인터] 백준 2470 두 용액

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

2470번: 두 용액

수행시간 : 1시간 / 난이도 : 골드 5

 

처음 풀어보는 투포인터라는 자료구조 문제였다. 

문제를 풀면서 느낀 투포인터는 start값과 end값을 조절하면서 값을 비교해주기에 start에 포인터하나 end에 포인터하나 즉 2개의 포인터를 통해서 값을 찾아나가는 알고리즘이었다.

B-search와 비슷한 맥략을 가진 자료구조지만, 항상 벡터의 인덱스를 가지고 조절을 하는 부분이 다르다.

 

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <math.h>
using namespace std;

int n;
vector<int> v;
pair<int, int> ans;

void input() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n;
	v.resize(n);
	for (int i = 0; i < n;++i) {
		cin >> v[i];
	}
	sort(v.begin(), v.end());
}
void sol() {
	int max_val = v.size() - 1;
	int min_val = 0;
	int init_val = pow(2, 32);
	int sum; //초기값
	while (min_val < max_val) {
		sum = v[max_val] + v[min_val];
		if (abs(sum) < abs(init_val)) {
			init_val = sum;
			ans.first = max_val;
			ans.second = min_val;
		}
		if (sum < 0) {
			min_val += 1;
		}
		else if (sum > 0) {
			max_val -= 1;
		}
		else {
			break;
		}
	}
	cout << v[ans.second] << " " << v[ans.first];
}
int main() {
	input();
	sol();
}