취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 2473번 문제인 세 용액이다.
문제는 아래 링크를 확인하자.

www.acmicpc.net/problem/2473

이 문제는 주어진 5000개의 정수 중 3개의 정수를 합해 만들 수 있는 0에 가장 가까운 정수를 만들 수 있는 세 정수를 출력하는 문제이다.

들어온 N개의 정수를 정렬하고, 가장 작은 정수서부터 그 정수를 포함하는 0에 가장 가까운 합을 투포인터를 이용하여 계산해내면 O(N^2)의 시간 내로 문제를 해결할 수 있다.

아래는 제출한 소스코드이다.

#include <iostream>
#include <algorithm>
typedef long long ll;
using namespace std;

ll liq[5000];

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

	int N; cin >> N;

	for (int i = 0; i < N; i++) {
		cin >> liq[i];
	}

	sort(liq, liq + N);

	ll ans = 999999999999999LL;
	ll a, b, c;
	for (int i = 0; i < N; i++) {
		ll liqi = liq[i];
		int L = i + 1, R = N - 1;
		while (L < R) {
			ll current = liq[L] + liq[R] + liqi;
			if (abs(current) < ans) {
				ans = abs(current);
				a = liqi, b = liq[L], c = liq[R];
			}
			if (current < 0) L++;
			else R--;

		}
	}

	cout << a << ' ' << b << ' ' << c;
}