백준 2473번 : 세 용액 (C++)

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

2473번: 세 용액

 

정수 배열에서 3개의 수를 골라 그 3개의 합이 최대한 0에 가까운 조합을 찾는문제이다. 먼저 N의 범위를 보자. N의 범위는 5000이하인 수로 O(N^2) 방법으로 시간내 풀 수 있음을 추측가능하다.

만약 골라야 하는 수가 3개가 아니고 2개라면 투 포인터나 해쉬맵으로 쉽게 해결할 수 있을 것이다.  그런 경우에는 배열의 사전에 정렬해줘야하므로 O(NlogN + N)의 복잡도를 가진다. 그럼 만약 골라야하는 수 1개는 고정시켜두고 나머지에 대해서만 투 투인터 방법을 사용하는것은 어떨까? 즉 3번째 수를 일단 골랐다고 하면 4번째수 ~ N번째 수에 대해서만 투 포인터로 타겟들을 찾는것이다. 그럼 시간복잡도가 O(NlogN + N^2) = O(N^2)으로 시간내에 충분히 풀 수 있다.

 

 

 

	#include <iostream>
	#include <vector>
	#include <algorithm>
	#include <cmath>
	#include <set>
	#include<map>
	#include <queue>

	typedef long long ll;

	using namespace std;
	int n;
	ll p[100002];


	int main()
	{
		cin.tie(NULL);
		ios::sync_with_stdio(false);
		
		cin >> n;

		for(int i=1; i<=n; i++){
			cin >> p[i];
		}

		
		sort(&p[1], &p[n+1]);

		ll sum = INT64_MAX;
		ll a1, a2, a3;
		for(int i=1; i<=n; i++){
			int j = i+1;
			int k = n;
			while(j < k){
				if(sum > abs(p[i] + p[j] + p[k])){
					sum = abs(p[i] + p[j] + p[k]);
					a1 = p[i];
					a2 = p[j];
					a3 = p[k];
				}

				if(p[i] + p[j] + p[k] < 0){
					j++;
				}
				else{
					k--;
				}
			}
		}

		cout << a1 << ' ' << a2 << ' ' << a3;
	}