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

문제

 

풀이

-10억부터 10억까지 숫자가 주어지고 세 수의 합이 가장 0에 가까운 수들을 찾는 문제이다.

입력은 정렬된 상태로 주어지지 않으니, 입력을 받고 먼저 정렬을 한다.

반복문으로 배열에 접근하면서 투 포인터를 사용하였다.

abs(arr[i] + arr[low] + arr[high])가 가장 0에 가까운 세 수를 찾으면 되는데,

10억 + 10억 + 10억은 int로 받을시에 오버플로가 나서 long long으로 받아주었다.

 

코드

#include <iostream>
#include <algorithm>
#include <cmath>
#include <limits.h>
using namespace std;

int n;
int arr[5001];

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

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

    sort(arr, arr + n);

    long long sum = LLONG_MAX;
    int answer1, answer2, answer3;
    for (int i = 0; i < n-2; i++) {
        int low = i + 1;
        int high = n - 1;
        while (low != high) {
            long long tempSum = (long long)arr[i] + (long long)arr[low] + (long long)arr[high];
            if (abs(tempSum) < sum) {
                sum = abs(tempSum);
                answer1 = arr[i];
                answer2 = arr[low];
                answer3 = arr[high];
            }
            if (abs(arr[i]) > abs(arr[low] + arr[high]))
                low++;
            else 
                high--;
        }
    }

    cout << answer1 << " " << answer2 << " " << answer3;

    return 0;
}