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

 

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

2473번: 세 용액

#문제 간단 정리

이전의 두 용액 문제와 같이 

두 포인터를 사용한 문제

#문제 해결 방법

이전의 두 용액에서와는 달리

첫번째 용액을 고르고 

두번째와 세번째를 두 포인터로 좌 우를 조절하며 가장 0과 가까운 용액을 찾는다.

 

그리고.. 그냥 첫번째와 두번째 용액을 브루트 포스로 전부 탐색하고

세번 째 용액을 이진탐색으로 고르는 방법이 있다.

이게 좀 더 복잡하다.

#전체 코드

1번 코드 (두 포인터)

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

typedef long long ll;

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

    int N;
    cin >> N;  // N의 값을 입력받습니다.

    vector<ll> liquids(N);

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

    sort(liquids.begin(), liquids.end());

    ll closestSum = LLONG_MAX;
    int trueAnswers[3] = { -1, -1, -1 };

    // 첫 번째 용액을 고정합니다.
    for (int i = 0; i < N - 2; i++) {
        int left = i + 1;
        int right = N - 1;
        
        // 두 번째와 세 번째 용액을 탐색합니다.
        while (left < right) {
            ll sum = liquids[i] + liquids[left] + liquids[right];
            if (abs(sum) < abs(closestSum)) {
                closestSum = abs(sum);  // 최소 합을 업데이트합니다.
                trueAnswers[0] = liquids[i];
                trueAnswers[1] = liquids[left];
                trueAnswers[2] = liquids[right];
            }
            
            // 합을 조절하여 0에 더 가까운 조합을 찾습니다.
            if (sum > 0) {
                right--;
            } else {
                left++;
            }
        }
    }

    cout << trueAnswers[0] << " " << trueAnswers[1] << " " << trueAnswers[2] << '\n';
    return 0;
}

2번코드 (이진탐색)

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

typedef long long ll;

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

    int N;
    cin >> N;
    vector<ll> liquids(N);

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

    sort(liquids.begin(), liquids.end());

    ll closestSum = LLONG_MAX;
    int resA = 0, resB = 0, resC = 0;

    for (int i = 0; i < N; ++i) {
        for (int j = i + 1; j < N; ++j) {
            int left = j + 1, right = N - 1;

            while (left <= right) {
                int mid = left + (right - left) / 2;
                ll sum = liquids[i] + liquids[j] + liquids[mid];

                if (abs(0 - sum) < closestSum) {
                    closestSum = abs(0 - sum);
                    resA = i, resB = j, resC = mid;
                }

                if (sum > 0) right = mid - 1;
                else if (sum < 0) left = mid + 1;
                else break; // sum이 0인 경우, 최적의 조합을 찾음
            }
        }
    }

    cout << liquids[resA] << " " << liquids[resB] << " " << liquids[resC] << '\n';
    return 0;
}