[ BOJ 백준 2470번 - 두 용액 ] 해설 및 코드

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

 

 

목적

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

 

접근법

투 포인터 알고리즘으로 구현이 가능하다.(완전 탐색이나 이분 탐색보다 빠르고 간단하다.) 투 포인터 알고리즘은 다음과 같이 정렬된 배열이 있다면, 배열의 처음과 끝을 가리키는 L과 R을 서로가 가까워지도록 이동하는 방식으로 동작한다.

 

초기 상황을 제외하고 최대 N-2번의 포인터 이동이 있는데, 각 턴마다 두 포인터가 가리키는 수의 합이 0에 수렴하도록 한 개의 포인터를 이동해야 한다. 즉, 수의 합이 양수일 때는 R을 이동하여 합을 줄여주고, 음수일 때는 L을 이동하여 합을 늘려준다. 동시에 절대값의 최소값을 갱신해주면 된다.

 

 

이 과정을 이차원 배열 형태로 보면 다음과 같다. 처음 (A,F)지점 부터 (A,E)를 거쳐 (C,D)지점 까지 이동하며 N-1번의 탐색으로 답을 구할 수 있게 된다. 포인터 이동 규칙에 따라 건너 뛰게 되어 탐색되지 않은 지점의 값은 양의 무한대나 음의 무한대로 발산하므로 굳이 볼 필요가 없는 것이다.

 

#include<bits/stdc++.h>
#define f(i,l,r) for(int i=l;i<r;++i)
using namespace std;
int n,a[(int)1e5],s[2];

void sol(){
	int l=0,r=n-1,mn=2e9;
	while(l<r){
		int sum=a[l]+a[r];
		int tmp=abs(sum);
		if(mn>tmp)s[0]=l,s[1]=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();
	cout<<a[s[0]]<<' '<<a[s[1]];
	return 0;
}

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

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