[알고리즘] C++ 백준 2467 용액

백준 2467

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

2467번: 용액

풀이 전 나의 생각

N개의 산성 용액과 알칼리성 용액 배열이 주어진다. 

산성 용액 + 알칼리성 용액, 산성 용액 + 산성 용액, 알칼리성 용액 + 알칼리성 용액 중

0에 가장 가까운 값을 찾아야한다.

 

N은 2이상 10만이하의 정수, 용액은 -10억 이상 10억 이하이다.(시간 제한 1초)

 

여기서 바로 해결할 수 있는 방법은 이중 for문을 돌며 하나 씩 탐색하며 계산을 해주는 것인데

10만 * 10만의 계산 횟수로 시간 제한 1초를 지키는 건 불가능하다.

따라서 탐색의 횟수를 줄일 수 있는 방법인 이진탐색을 이용하여 문제를 풀어야한다.

 

문제에서 입력 부분을 보면 용액은 오름차순으로 주어진다고 나와있다.

그러면 좌측에서 우측 방향으로는 용액이 커지고 우측에서 좌측 방향은 용액이 작아진다.

 

이를 통해 접근할 수 있는 탐색 방법은 좌측, 우측에서 탐색을 시작하여 

현재 합친 용액의 양이 0보다 작다면 용액을 추가해줘야 하니 우측에서 좌측,

현재 합친 용액의 양이 0보다 크면 용액을 줄여줘야 하니 좌측에서 우측 으로 한 칸씩

움직이면서 탐색하는 것이다.

 

이런 방식으로 접근하면 모든 경우의 수를 탐색하는 것이 아닌

원하는 부분만 탐색을 하기 때문에 탐색 계산 횟수가 현저히 줄어든다.

 

 

현재 좌측, 우측의 용액을 합친다.

int liq = all_liq[start] + all_liq[end];

 

이전 용액보다 현재 용액이 0보다 가깝다면 값을 갱신 해준다.

if (abs(liq) < prev_liq)
{
	fir_ans = all_liq[start];
	sec_ans = all_liq[end];
	prev_liq = abs(liq);
}

 

여기서 합친 용액의 값을 절대값으로 바꿔주는 이유는 0으로부터 합친 용액이 얼마나 가까운지 판단해야하기 때문이다.

만약 절대값을 적용해주지 않으면 용액의 대소 관계 비교가 되버려 올바른 값이 나오지 않게 된다.

(0부터 가까운값이 아닌 합친 용액이 얼마나 작은지 비교하게 됨)

 

합친 용액의 양에 따라 우측과 좌측의 값을 변경시켜준다.

if (liq < 0)
{
	start++;
}
else
{
	end--;
}

 

풀이

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <string>
#include <queue>
#include <string.h>
#include <limits.h>
#include <cstdio>

using namespace std;

int all_liq[100001];
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	int N, fir_ans, sec_ans;
	int prev_liq = INT_MAX;

	cin >> N;

	int start = 0;
	int end = N - 1;

	for (int i = 0; i < N; i++)
	{
		cin >> all_liq[i];
	}

	while (start < end)
	{
		int liq = all_liq[start] + all_liq[end];

		if (abs(liq) < prev_liq)
		{
			fir_ans = all_liq[start];
			sec_ans = all_liq[end];
			prev_liq = abs(liq);
		}

		if (liq < 0)
		{
			start++;
		}
		else
		{
			end--;
		}
	}

	cout << fir_ans << " " << sec_ans;
}