백준 2473번 C++ 풀이

문제

 

시간 제한	메모리 제한	solved.ac 티어
1초	256MB	골드 3

---

풀이

이번에도 밀린 문제 정리하기다. 저번에는 두 용액이었지만, 이번엔 세 용액이다. 두 용액에 대한 문제는 다음 글을 참고하자.

https://codejin.tistory.com/270

백준 2470번 C++ 풀이

 

용액이 세개로 늘어났다고 해서 쫄 필요가 없다. 이 문제도 투포인터로 풀이가 가능하다. 이 문제를 브루트포스로 푼다면 O(N^3)이 나올 것이다. 5000^3은 1250억이다. 당연히 안될 것이다. 하지만 해당 문제를 투포인터로 풀게 되면 O(N^2)이 된다. 투포인터의 시간복잡도는 O(N)이지만, 반복문을 통해 하나의 용액을 결정하고, 이후 투포인터를 돌려가며 세 특성값의 합이 0에 근접하는 값을 찾으면 된다.

코드

#include <bits/stdc++.h>
#define ALL(X) X.begin(), X.end()
using namespace std;
using ll = long long;

int n;
vector<ll> v;

void input(){
    cin >> n;
    v.resize(n);
    for(ll& x : v) cin >> x;
    sort(ALL(v));
}
    
void sol(){
    vector<ll> answer;
    ll diff = INT64_MAX;

    for(int i = 0; i < n; i++){
        int l = 0, r = n-1;
        ll cur_diff;
        
        while(l < r) {
            if (l == i) {
                l++;
                continue;
            }
            if (r == i){
                r--;
                continue;
            }
            cur_diff = v[i] + v[l]+v[r];
            if (diff > abs(cur_diff)){
                diff = abs(cur_diff);
                answer = {v[l], v[r], v[i]};
            }
            if (cur_diff < 0) l++;
            else r--;
        }
    }
    sort(ALL(answer));
    for (ll& a : answer) cout << a << ' ';
}

int main(){
    cin.tie(0)->sync_with_stdio(0);
    input();
    sol();
}

당시 핸드폰으로 푸느라 오타가 많아 생긴 무수한 컴파일에러