[백준]2473번 세 용액 - C/C++

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

2473번: 세 용액

문제

KOI 부설 과학연구소에서는 많은 종류의 산성 용액과 알칼리성 용액을 보유하고 있다. 각 용액에는 그 용액의 특성을 나타내는 하나의 정수가 주어져있다.  산성 용액의 특성값은 1부터 1,000,000,000까지의 양의 정수로 나타내고, 알칼리성 용액의 특성값은 -1부터 -1,000,000,000까지의 음의 정수로 나타낸다.

같은 양의 세 가지 용액을 혼합한 용액의 특성값은 혼합에 사용된 각 용액의 특성값의 합으로 정의한다. 이 연구소에서는 같은 양의 세 가지 용액을 혼합하여 특성값이 0에 가장 가까운 용액을 만들려고 한다. 

예를 들어, 주어진 용액들의 특성값이 [-2, 6, -97, -6, 98]인 경우에는 특성값이 -97와 -2인 용액과 특성값이 98인 용액을 혼합하면 특성값이 -1인 용액을 만들 수 있고, 이 용액이 특성값이 0에 가장 가까운 용액이다. 참고로, 세 종류의 알칼리성 용액만으로나 혹은 세 종류의 산성 용액만으로 특성값이 0에 가장 가까운 혼합 용액을 만드는 경우도 존재할 수 있다.

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

입력

첫째 줄에는 전체 용액의 수 N이 입력된다. N은 3 이상 5,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,000,000 이하이다. N개의 용액들의 특성값은 모두 다르고, 산성 용액만으로나 알칼리성 용액만으로 입력이 주어지는 경우도 있을 수 있다.

출력

첫째 줄에 특성값이 0에 가장 가까운 용액을 만들어내는 세 용액의 특성값을 출력한다. 출력해야하는 세 용액은 특성값의 오름차순으로 출력한다. 특성값이 0에 가장 가까운 용액을 만들어내는 경우가 두 개 이상일 경우에는 그 중 아무것이나 하나를 출력한다.

---

 

    세 숫자를 더해 0에 가까운 수를 만드는 문제이다. 0에 가까워 지게 만들어야 하니 배열을 정렬 한 뒤 투포인터를 사용하여  제일 처음 값과 제일 뒷 값을 더한 다음 수들의 합이 양수이면 큰 값을 작게 해 주고 음수이면 작은 값을 크게 하는 방식으로 문제를 풀고 싶다.

   

    하지만 투포인터와 다르게 이 문제는 세 가지 용액을 골라야 한다. 그러므로 한 용액을 고정해놓은 다음 나머지 용액들로 투 포인터를 해야 한다. 중복되는 경우가 없도록 투포인터의 작은 값의 포인터를 정할 때 고정해놓은 용액의 다음부터 시작한다면 중복되는 경우가 없다.

   

    추가로 유의해야할 점은 아래와 같이 입력 값은 10억으로 int형 범위에 들어와서 용액의 값을 저장하는 배열을 int, 세 용액의 합을 구하는 임시 변수는 long long으로 설정하여 풀면 오버플로우가 일어난다.

vector <int> arr;

long long temp = arr[s1] + arr[s2] + arr[s3]

그 이유는 저장하는 변수의 형과는 관계없이 int 형 변수 3개를 더하면 int 값에 저장된 뒤 long long 인 temp로 옮겨지기 때문에 int 값에 저장되는 부분에서 오버플로우가 일어나기 때문이다. 그러므로 애초에 vector를 long long으로 설정해두던지 덧셈을 할 때 한 변수를 long long으로 명시적 형 변환을 하여 더한 값이 long long에 저장된 뒤 temp에 저장될 수 있도록 하면 된다.

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

vector <int> arr;
int n;
int ans[3] = { 0 };
bool flag = false;
long long minval = 4'000'000'001;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int a,s1,s2,s3;
	long long temp;
	cin >> n ;
	for (int i = 0; i < n; i++) {
		cin >> a;
		arr.push_back(a);
	}
	sort(arr.begin(), arr.end());

	for (int k = 0; k < n-2; k++) {
		s1 = k; 
		s2 = k+1;
		s3 = n - 1;
		while (s2 != s3) {
			temp = (long long)arr[s1] + arr[s2] + arr[s3];
			
			if ( abs(temp) < minval) {
				minval = abs(temp);
				ans[0] = arr[s1]; ans[1] = arr[s2]; ans[2] = arr[s3];
				if (temp == 0) {
					flag = true;
					break;
				}
			}

			if (temp > 0) {
				s3--;
			}
			else {
				s2++;
			}
			
		}
		if (flag) break;
	}
	
	cout << ans[0] << " " << ans[1] << " " << ans[2];

	return 0;
}

---

    다른 골드 3 난이도의 문제를 먼저 풀었는데 플로이드 워샬 문제로 5분도 채 안 걸려서 문제를 푸는 바람에 양심에 찔려 다른 문제를 선택하여 풀었다. 이 문제를 어디선가 본 것 같은 느낌이 들었는데 친구의 블로그에 있던 문제였다. 포인터를 쓰는 것 까지는 진행하였는데 틀렸습니다가 나왔다. 알고리즘이 비교적 짧고 간결하여 알고리즘 문제보다는 범위 문제일 것이라고 생각을 하였다. 알고 보니 세 값을 더한 다음 변수에 저장하는 것인데 그 부분을 간과한 것이었다. 그래도 CS지식을 학기 중에 공부하다 보니 이러한 에러는 금방금방 이해가 되는 것 같아서 다행이다!