C++ / 2470 / 두 용액 ( 이분 탐색 )

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

문제 요약

KOI 부설 과학연구소에서는 많은 종류의 산성 용액과 알칼리성 용액을 보유하고 있습니다.

각 용액에는 그 용액의 특성을 나타내는 하나의 정수가 주어져있습니다.

산성 용액의 특성값은 1부터 1,000,000,000까지의 양의 정수로 나타내고, 알칼리성 용액의 특성값은 -1부터 -1,000,000,000까지의 음의 정수로 나타냅니다.

같은 양의 두 용액을 혼합한 용액의 특성값은 혼합에 사용된 각 용액의 특성값의 합으로 정의합니다.

이 연구소에서는 같은 양의 두 용액을 혼합하여 특성값이 0에 가장 가까운 용액을 만들려고 합니다.

예를 들어, 주어진 용액들의 특성값이 [-2, 4, -99, -1, 98]인 경우에는 특성값이 -99인 용액과 특성값이 98인 용액을 혼합하면 특성값이 -1인 용액을 만들 수 있고, 이 용액이 특성값이 0에 가장 가까운 용액입니다.

참고로, 두 종류의 알칼리성 용액만으로나 혹은 두 종류의 산성 용액만으로 특성값이 0에 가장 가까운 혼합 용액을 만드는 경우도 존재할 수 있습니다.

산성 용액과 알칼리성 용액의 특성값이 주어졌을 때, 이 중 두 개의 서로 다른 용액을 혼합하여 특성값이 0에 가장 가까운 용액을 만들어내는 두 용액을 찾는 프로그램을 작성해야합니다.

 

이 문제는 이 전에 풀었던 용액 문제와 거의 동일합니다.

https://lgj415415.tistory.com/120

C++ / 2467 / 용액 ( 두 포인터 )

 

문제 풀이

1. 용액의 개수와 용액을 입력받아 정렬합니다.

2. 용액들을 투포인터 탐색하는데, 시작 값으로는 0 끝 값으로는 마지막 용액을 줍니다.

3. 용액의 합은 초기값으로 2000000001을 줍니다.

4. 시작 값 용액과 마지막 용액의 합이 기존의 용액의 합 보다 크면 음수일 경우 시작값을 + 1 해주고 양수일 경우 끝 값 -1 합니다.

5. 기존의  용액의 합보다 작을 경우에는 용액의 합을 갱신하고 현재 용액들을 저장합니다. 

6. 용액의 합이 음수면 시작값 +1 하고 양수면 끝 값 -1을 합니다.

7. 두 용액을 출력합니다.

주의할 점

이전의 용액 문제와 똑같이 sum의 초기값을 2000000001을 줘야합니다.

그리고 이번에 했던 실수는 현재 용액의 합이 과거의 용액의 합보다 작을경우에 시작값과 끝값을 양수 음수에 맞춰 증감 시켜야 하는 데 그 부분을 까먹고 풀었다가 실수 했던 것 같습니다.

 

아래 예제 2와 예제 3은 풀면서 도움이 됐던 예제 입니다.

코드

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

using namespace std;
typedef long long int ll;

ll n, a, b;
vector<ll>v;

void bs()
{
	ll start = 0;
	ll end = v.size() - 1;
	ll sum = 2000000001, temp = 0;
	while (start < end)
	{
		temp =v[start] + v[end];
		// 용액의 합이 기존것 보다 크면
		if (abs(temp) > sum)
		{
			// 용액의 합이 음수면
			if (temp < 0)
			{
				start += 1;
			}// 용액의 합이 양수면
			else
			{
				end -= 1;
			}

		}
		else
		{
			// 용액의 합이 기존 것 보다 작으면 갱신
			sum = abs(temp);
			a = v[start];
			b = v[end];
			// 음수면
			if (temp < 0)
			{
				start += 1;
			}
			// 양수면
			else
			{
				end -= 1;
			}
		}

	}
	return;

}
int main()
{
	cin >> n;

	for (ll i = 0; i < n; i++)
	{
		ll a;
		cin >> a;
		v.push_back(a);
	}
	sort(v.begin(), v.end());
	bs();
	cout << a << " " << b;
	return 0;
}

예제 1

5
-2 4 -99 -1 98

결과 1

예제 2

6
1 2 3 4 5 6

결과 2

예제 3

3
-5 -2 -1

결과 3