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

백준 2473

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

2473번: 세 용액

풀이 전 나의 생각

산성 용액과 알칼리성 용액이 주어질 때 세 용액을 합해서 나온 값이 0에 가장 가까운

용액들을 구해야한다.

 

조건

- N개의 정수 모두 -1,000,000,000 이상 1,000,000,000 이하

- N은 3 이상 5,000 이하의 정수

- 산성 용액만으로나 알칼리성 용액만으로 입력이 주어지는 경우도 있을 수 있다.

 

과정

1. N개의 정수 즉, 용액의 범위는 -10억 ~ 10억이다. 현재 세 용액을 합쳐야 하기 때문에

10억을 3번 더하면 int형의 범위를 초과하여 데이터 타입을 long으로 지정해준다.

 

2. 산성 용액과 알칼리성 용액만으로 주어지기 때문에 모든 경우를 탐색해야한다.

 

3. N이 5000개 주어졌을 때 세 용액을 탐색하기 위해 for문만 사용할 시 많은 계산횟수가 나오기 때문에

이분탐색을 이용하여 풀어야한다.

 

 

1.  세 용액을 선택하기 위해 용액 하나를 고정하고 탐색할 시작 용액과 끝 용액을 지정해준다.

for (int i = 0; i < N - 1; i++)
	{
		int start = i + 1;
		int end = N - 1;
        ...

현재 세 용액을 선택해서 이 값을 기준으로 이분탐색을 진행해야한다.

그럼 첫 번째 용액부터 증가하며 차례대로 고정 값을 둔다면 손쉽게 모든 경우의 수를 효율적로 구할 수 있을 것이다.

예를 들어  (-97 -6 -2 6 98)의 용액 배열이 있다고 가정하면 첫 번째 고정 용액은 -97이며 시작 과 끝 용액은

-6 과 98이다. 그럼 -97 용액이 기준일 때 -6 ~ 98을 탐색하며 최적의 값을 찾아낸다. 

다음으로 -6 용액이 기준이 되고 -2 ~ 98을 탐색하며 최적의 값을 찾아낸다.

(-97은 이미 최적의 값을 찾아냈으니 탐색할 필요가 없다.)

 

이처럼 어느 용액을 고정했을 때 나올 수 있는 최적의 값을 찾아낸다면

결국 얻고자 하는 0에 가까운 세 용액의 합을 구해낼 수 있다.

 

2. 세 용액을 더한 양이 이전 값보다 작다면 값을 갱신 시켜준다.

while (start < end)
		{
			long comp_liq = liq[start] + liq[end] + liq[i];

			if (abs(comp_liq) < equ_val)
			{
				equ_val = abs(comp_liq);
				ans[0] = liq[i];
				ans[1] = liq[start];
				ans[2] = liq[end];
			}
			....

 

3. 세 용액의 합이 0보다 작다면 시작 위치를 증가, 0보다 크다면 끝 위치를 감소한다.

if (comp_liq < 0) start++;
else end--;

(-97 -6 -2 6 98) 의 용액 배열에서 -97의 고정 용액과 시작과 끝 용액 -6, 98 이 있다고 가정할 때

최적 값을 찾기 위해선 세 용액의 합이 0보다 작다면 시작 위치를 증가시켜줘야한다.

-> 세 용액의 합이 -6이라면 0에 가까워지기 위해 값을 올려주며 탐색한다.

 

세 용액의 합이 0보다 크다면 끝 위치를 감소시켜줘야한다.

-> 세 용액의 합이 6이라면 0에 가까워지기 위해 값을 내려주며 탐색한다.

 

 

 

풀이

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

using namespace std;

int liq[5001];
int ans[3];

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	int N;
	long equ_val = LONG_MAX;
	cin >> N;

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

	sort(liq, liq + N);

	for (int i = 0; i < N - 1; i++)
	{
		int start = i + 1;
		int end = N - 1;

		while (start < end)
		{
			long comp_liq = liq[start] + liq[end] + liq[i];

			if (abs(comp_liq) < equ_val)
			{
				equ_val = abs(comp_liq);
				ans[0] = liq[i];
				ans[1] = liq[start];
				ans[2] = liq[end];
			}

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

	cout << ans[0] << " " << ans[1] << " " << ans[2];
}