백준 - 2470번 두 용액 (C++)

https://www.acmicpc.net/status?from_mine=1&problem_id=2470&user_id=als982001&language_id=1001 

채점 현황

 이 문제는 용액들의 개수와 특성값들이 주어졌을 때, 가장 합의 크기(절댓값)를 작게 만들 수 있는 용액 두 개를 출력하는 문제이다. 이는 이분 탐색을 통해 풀 수 있는 문제이다. 그런데 이분 탐색을 위해서는 데이터가 정렬되어 있어야 한다. 하지만 당장 예제만 보더라도 용액들의 특성값들이 정렬되어 있지 않다. 하지만 걱정할 것은 없다. 왜냐하면 이 문제는 용액들의 인덱스 값을 출력하는 문제가 아니라 용액들의 특성값을 출력하는 문제이기 때문에 별 걱정 없이 정렬 후 이분 탐색을 진행하면 된다. 이 문제를 풀기 위해 구상한 절차는 다음과 같다.

1. 각 값들을 입력 받는다.
2. 용액들의 특성값을 오름차순으로 정렬한다.
3. 이분 탐색을 실시한다.
   1. 처음 시작할 때, 두 개의 인덱스는 각각 0과 용액의 개수 - 1로 설정한다.
   2. 만약 두 용액의 합의 절댓값이 저장되어 있던 값보다 작다면 답을 갱신한다.
   3. 만약 두 용액의 합이 0이라면, 바로 두 인덱스의 값을 반환한다.
   4. 만약 현재 용액의 합이 0보다 크다면, 용액의 합의 크기를 줄여야 하기 때문에 뒤쪽 인덱스의 값을 줄인다. (오름차순 정렬이기 때문)
   5. 만약 현재 용액의 합이 0보다 작다면, 용액의 합의 크기를 늘려야 하기 때문에 앞쪽 인덱스의 값을 키운다.
   6. 2번으로 돌아간다.

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <algorithm>
#include <queue>
#include <memory.h>
#include <deque>
#include <cmath>
#include <stack>
#include <cstring>
#include <typeinfo>
#include <iomanip>
#include <limits.h> 
#include <map>
#pragma warning(disable:4996)

using namespace std;

#define TARGET 0

int N;
vector<long long> liquidValues;

vector<long long> Check()
{	
	vector<long long> answer(2, 0);
	answer[0] = liquidValues.front();
	answer[1] = liquidValues.back();

	long long mixedValue = abs(liquidValues.front() + liquidValues.back());

	int front = 0;
	int back = N - 1;

	while(front < back)
	{
		long long curMixedValue = liquidValues[front] + liquidValues[back];

		if (mixedValue > abs(curMixedValue))
		{
			mixedValue = abs(curMixedValue);

			answer[0] = liquidValues[front];
			answer[1] = liquidValues[back];
		}		

		if (mixedValue == 0)
			return answer;
		else if (curMixedValue > 0)
			--back;
		else
			++front;
	}

	return answer;
}

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

	cin >> N;

	for (int i = 0; i < N; ++i)
	{
		long long liquidValue;
		cin >> liquidValue;

		liquidValues.push_back(liquidValue);
	}

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

	vector<long long> answer = Check();
	
	cout << answer[0] << " " << answer[1] << endl;

	return 0;
}

 

---

참고: https://ko.wikipedia.org/wiki/%EC%9D%B4%EC%A7%84_%EA%B2%80%EC%83%89_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98