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

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

 

 

이 문제는 이전 비슷한 문제 두 용액 문제와 비슷한 문제이다.

서로 다른 용액의 크기가 주어졌을때 3개의 용액을 합하여 용액의 크기가 0에 가깝게 만드는 용액을 출력하는 문제이다.

 

용액의 수가 최대 5000 이기 때문에 완전탐색 O(N^3) -> 10억 정도 들기 때문에 시간초과가 난다.

 

따라서 O(N)으로 최적으로 풀 수 있는 알고리즘을 사용해서 풀어야 한다.

 

 

따라서 O(N)으로 풀기 위해서 두포인터 알고리즘을 사용하는데 다른 하나의 포인터를 임의로 고정시켜서 모든 요소를 하나씩 선택하여 구하였다.

이때 오른쪽 포인터는 배열 끝을 선택하여 안쪽으로 좁혀나가는 방식으로 구하였다.

그 이유는 음수가 있기 때문에 0에 가깝게 하기위한 차이를 구하기 위해서이다.

 

정답 코드

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
#define endl "\n"
#define MAX 3e9

int dx[] = {-1, 0, 1, 0, 1, -1, -1, 1};
int dy[] = {0, 1, 0, -1, -1, 1, -1, 1};
int N;
vector<ll> v;
ll res1, res2, res3;

void solve() {
    sort(v.begin(), v.end());
    ll minval = MAX;

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

        while(left < right) {
            ll val = v[i] + v[left] + v[right];

            ll vals = abs(val);

            if(minval > vals) {
                minval = vals;
                res1 = v[i];
                res2 = v[left];
                res3 = v[right];
            }

            if(val == 0) {
                cout << v[i] << " " << v[left] << " " << v[right];
                exit(0);
            }
            else if(val > 0) right--;
            else left++;
        }
    }

    cout << res1 << " " << res2 << " " << res3;
}

void input() {
    cin >> N;

    for(int i = 0; i < N; i++) {
        ll a;
        cin >> a;
        v.push_back(a);
    }
}

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

    input();
    solve();
}

 

 

회고록

자꾸 범위 설정을 int로 하는 것이 버릇이 되서 크기를 설정할때 유심히 봐야하는 습관이 필요한것 같다.

3개의 합이 최대 3억이 될 수 있기 때문에 차이를 좁혀나가는 과정에서 차이값을 3억으로 설정해야했었는데

1억으로 설정하여 중간에 틀렸다