[ BOJ 백준 2473번 - 세 용액 ] 해설 및 코드

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

 

 

목적

용액의 특성값들이 N개 주어질 때, 3가지의 특성값을 더해 절대값이 0에 가장 가까운 용액의 특성값들을 구하자.

 

접근법

첫 번째 용액이 정해진 상태라면, 나머지 두 개의 용액을 선택하여 절대값이 0에 가깝도록 하는 것은 투 포인터 알고리즘으로 구할 수 있다. (투포인터 알고리즘에 대한 설명은 다음 글 참조 [백준 2470 - 두 용액]) 

 

첫 번째 용액으로 선택할 수 있는 용액의 수는 총  N-2개이며, 이 용액의 특성값을 더하여 절대값이 0에 가까운 값을 만들기 위한 나머지 두 개의 용액만 구하면 된다.

 

#include<bits/stdc++.h>
#define f(i,l,r) for(int i=l;i<r;++i)
#define fr(i,l,r) for(int i=l;i>=r;--i)
using namespace std;
typedef long long ll;
int n,a[5000],s[3];

void sol(){
	ll mn=3e9;
	fr(i,n-3,0){
		int l=i+1,r=n-1;
		while(l<r){
			ll sum=(ll)a[i]+a[l]+a[r],tmp=abs(sum);
			if(mn>tmp)s[0]=i,s[1]=l,s[2]=r,mn=tmp;
			if(!sum)return;
			sum>0?--r:++l;
		}
	}
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin>>n;
	f(i,0,n)cin>>a[i];
	sort(a,a+n);
	sol();
	f(i,0,3)cout<<a[s[i]]<<' ';
	return 0;
}

문제 설명과 코드에 대한 피드백은 언제나 환영합니다.

 다양한 의견 댓글로 남겨주세요.