백준 2473 세 용액 (c++) : 피너클

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

2473번: 세 용액

투 포인터 문제다.

 

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

값을 입력받은 뒤 정렬한다.

long long ans[3] = { 0, 0, 0 };
long long m = 9876543210;

ans에는 세 용액이 들어가고 m에는 세 용액의 합이 들어간다.

이제 투포인터로 답을 구할것이다. 이때 세 용액을 구해야 하는데 투포인터는 2개의 숫자만 구할수있다.

그래서 숫자 하나는 고정으로 하고 투포인터를 돌릴것이다.

for (int i = 0; i < n; i++) {
	long long now = v[i];
	vector<int> sam;
	for (int j = 0; j < i; j++) sam.push_back(v[j]);
	for (int j = i + 1; j < n; j++) sam.push_back(v[j]);

n만큼 반복한다. now는 v[i]로 이것이 고정값이다.

벡터 sam에 v[i]를 제외한 모든 v값들을 넣는다.

	long long start = 0, end = n - 2;
	while (start < end) {
		long long sum = now + sam[start] + sam[end];
		if (abs(sum) < m) {
			ans[0] = sam[start];
			ans[1] = sam[end];
			ans[2] = now;
			m = abs(sum);
		}
		if (sum < 0) start++;
		else if (sum > 0) end--;
		else break;
	}

start는 0에서부터, end는 sam의 크기 - 1인 n - 2에서 부터 시작한다.

sum은 고정값 + sam[start] + sam[end] 이다.

만약 sum의 절대값이 m보다 작다면 ans를 모두 업데이트 한뒤 m로 sum의 절대값으로 업데이트한다.

만약 sum이 0보다 작다면 보다 높은 숫자를 더해야 하니 start++를 하고

만약 sum이 0보다 크다면 보다 낮은 숫자를 더해야 하니 end--를 한다.

둘다 아니라면 sum == 0이라는 뜻이니 다른건 볼 필요도 없다. 반복문에서 바로 나온다.

sort(ans, ans + 3);
for (int i = 0; i < 3; i++)cout << ans[i] << ' ';

이제 ans를 정렬하고 출력하면 끝이다.

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

long long n;
vector<long long> v;

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

	cin >> n;
	for (int i = 0; i < n; i++) {
		int a;
		cin >> a;
		v.push_back(a);
	}
	sort(v.begin(), v.end());
	
	long long ans[3] = { 0, 0, 0 };
	long long m = 9876543210;

	for (int i = 0; i < n; i++) {
		long long now = v[i];
		vector<int> sam;
		for (int j = 0; j < i; j++) sam.push_back(v[j]);
		for (int j = i + 1; j < n; j++) sam.push_back(v[j]);

		long long start = 0, end = n - 2;
		while (start < end) {
			long long sum = now + sam[start] + sam[end];
			if (abs(sum) < m) {
				ans[0] = sam[start];
				ans[1] = sam[end];
				ans[2] = now;
				m = abs(sum);
			}

			if (sum < 0) start++;
			else if (sum > 0) end--;
			else break;
		}
	}
	sort(ans, ans + 3);
	for (int i = 0; i < 3; i++)cout << ans[i] << ' ';
}

전체코드다.