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

 

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

 

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

2473번: 세 용액

---

 

해결전략

 

Two Pointer 투 포인터 

 

 

세 포인터를 사용하여 가능한 모든 용액의 조합을 검사하며, 그 중 합이 0에 가장 가까운 조합을 찾는다.

 

i를 중앙 포인터로 사용하여 p1과 p2를 양쪽으로 이동시키는 방식을 사용하였다. p1, i, p2가 각각 다른 용액을 가리키도록 유지하면서 가능한 모든 조합을 검사한다.

 

합이 0보다 작으면 왼쪽 포인터를 오른쪽으로 이동시켜 합을 증가시키고,

그렇지 않으면 오른쪽 포인터를 왼쪽으로 이동시켜 합을 감소시킨다. 이 과정을 반복하여 최소 합을 찾는다.

---

 

정답 코드

 

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

int n; // 용액의 수
vector<int> v; // 용액 정보를 담은 벡터
long long answer = 3000000000; // 최소 합을 저장할 변수, 초기값을 최대값으로 설정
int res1, res2, res3; // 최소 합을 갖는 세 용액

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	cin >> n;
	v.resize(n);
	for (int i = 0; i < n; i++) {
		cin >> v[i];
	}
	sort(v.begin(), v.end());

	// p1은 왼쪽 포인터, i는 중간 포인터, p2는 오른쪽 포인터
	for (int i = 1; i < n - 1; i++)
	{
		int p1 = 0, p2 = n - 1;
		while (p1 < i && i < p2)
		{
        	// 세 용액의 합 계산. 우변에 명시적으로 (long long) 안 적어주면 오버플로우 발생할 수 있음.
			long long sum = (long long)v[p1] + v[i] + v[p2]; 
			
            if (abs(sum) < abs(answer)) { // 계산된 합의 절댓값이 answer보다 작으면 answer 갱신하고, 해당 용액 정보 저장
				answer = sum;
				res1 = v[p1];
				res2 = v[i];
				res3 = v[p2];
			}

			if (sum < 0) { // 합이 0보다 작으면 왼쪽 포인터를 오른쪽으로 이동
				p1++;
			}
			else { // 합이 0보다 크면 오른쪽 포인터를 왼쪽으로 이동
				p2--;
			}
		}
	}

	cout << res1 << " " << res2 << " " << res3 << "\n";

	return 0;
}

 

 

---