백준 2470 두 용액 (c++) : 피너클

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

2470번: 두 용액

입력 받은 값들중 합이 0에 가까운 두 수를 찾는 문제다. 

n이 100000일때 이중 for문을 돌리면 시간초과가 나기에 모든 값을 찾아보는건 힘들다.

입력 받은 값들을 정렬시킨다음 투 포인터를 이용해 하나씩 합을 맞춰보면 간단하게 풀수 있다.

int a, b, sum = 2000000000;
int start = 0, end = n - 1;

int a와 b에는 합이 가장 작은 수의 위치가 들어갈것이고

sum에는 두 수의 합이 들어갈것이다. 이미 들어와있는 수는 입력받은 값으론 나올수 없는 큰 수이다.

int start는 투 포인터의 시작 부분, end는 투 포인터의 끝나는 부분이다.

while (start < end) {
	int m = v[start] + v[end];
	if (abs(sum) > abs(m)) {
		sum = m;
		a = start;
		b = end;
	}
	if (m < 0) start++;
	else if (m > 0) end--;
	else if (m == 0) break;
}

start가 end보다 낮은 동안 반복문을 돌린다.

int m에는 v[start]와 v[end[, 두 수의 합이 들어간다. (v는 vector<int> v, 값을 입력받은 배열)

만약 sum의 절대값이 m의 절대값보다 높다면 (절대값으로 하는 이유는 0에 가까운 수를 찾기 위함)

sum을 m으로 바꾸로 a에 start를, b에 end를 집어넣는다.

절대값이 높다는 것은 0에서 더 멀다는 뜻이다. (100이 1보다 0에서 멀듯이, -10이 1000보다 0에 더 가깝듯이)

 

만약 m이 0보다 작다면 두 수의 합을 크게 해줘야한다. start에 1을 더해준다.

만약 m이 0보다 크다면 두 수의 합을 작게 해줘야 한다. end에 1을 뺴준다.

만약 m이 0이면 다른건 찾아볼필요도 없이 반복문을 종료시킨다.

 

예를 들어 현재 배열은 정렬되어있는 상태, [-99, -2, -1, 4, 98] 인 상태다.

start는 0이고 end는 4인 상태에서 합은 -99 + 98인 -1이 된다.

합이 0보다 작으니 start에 1을 더해 start를 1로 만들어주면

start는 1이 되고 end는 4가 되어 둘의 합은 -2 + 98인 96이 된다. 

이제 다시 합이 0보다 크니 end에 1을 빼 end를 3로 만들어주면 합이 -2 + 4인 2가 된다.

이를 반복해서 0에 가까운 합을 찾아내는 것이다.

 

전체코드다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <string>

using namespace std;

int n;
vector<int> v;


int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n;
	v.resize(n);

	for (int i = 0; i < n; i++) cin >> v[i];

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

	int a, b, sum = 2000000000;
	int start = 0, end = n - 1;
	while (start < end) {
		int m = v[start] + v[end];
		if (abs(sum) > abs(m)) {
			sum = m;
			a = start;
			b = end;
		}

		if (m < 0) start++;
		else if (m > 0) end--;
		else if (m == 0) break;

	}
	cout << v[a] << ' ' << v[b] << endl;
}