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

 

두 용액과 비슷합니다. 투포인터로 풀면 됩니다.

투포인터 + 포인터 한개가 더 필요합니다. 즉 3개가 필요합니다.

 

일단 배열을 오름차순으로 정렬합니다.

i는 [0, n-3]이 되도록 하고, 반복문 안에서 j=i+1, k=n-1로 시작합니다. 그 뒤의 내용은 두 용액을 풀었을 때와 동일합니다.

이번에는 [-10억, 10억] 변수를 세 개를 더할 수 있으니 long long 등을 사용해 오버플로우를 방지해야 합니다.

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll INF = numeric_limits<ll>::max();

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr), cout.tie(nullptr);

	int n;
	cin >> n;
	vector<ll> v(n);
	for (auto& c : v)
		cin >> c;
	sort(v.begin(), v.end());

	bool zero = false;
	ll min_diff = INF;
	int pi, pj, pk;

	for (int i = 0; i < n - 2 && !zero; ++i) {
		int j = i + 1;
		int k = n - 1;

		while (j < k) {
			ll sum = v[i] + v[j] + v[k];
			if (min_diff > abs(sum)) {
				min_diff = abs(sum);
				tie(pi, pj, pk) = { i, j, k };
			}
			
			if (sum == 0) {
				zero = true;
				tie(pi, pj, pk) = { i, j, k };
				break;
			}
			else if (sum > 0)
				--k;
			else
				++j;
		}
	}

	cout << v[pi] << ' ' << v[pj] << ' ' << v[pk] << '\n';

	return 0;
}

중간에 합이 0이 되면 모든 반복문 바로 빠져나오게 했습니다. i가 있는 for문 조건에 !zero가 보이시죠?

여러개 변수를 묶어서 변경할 때 tie를 써봤는데 깔끔하네요. 뭐 pi=i, pj=j, pk=k;랑 타자 수 차이가 별로 안나긴 합니다.

반응형

'Online Judge > 백준' 카테고리의 다른 글

[백준][C++] 2993: 세 부분  (0) 2020.07.09
[백준][C++] 1806: 부분합  (0) 2020.07.08
[백준][C++] 2470: 두 용액  (0) 2020.07.08
[백준][C++] 1987: 알파벳  (0) 2020.07.08
[백준][C++] 12852: 1로 만들기 2  (0) 2020.07.08