BaekJoon 2473번: 세 용액(C++)

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

2473번: 세 용액

풀이법

1) 투 포인터를 활용하여 탐색을 진행했으며, 조건을 설정하여 문제를 해결하였다.

2) 투 포인터를 활용하기 위해 처음에 들어온 배열을 정렬하였다.

3) 기준이 될 용액을 잡기 위해 for문을 모든 index에 활용하였으며, 해당 index보다 하나 큰 것을 left, 배열의 마지막 index를 right를 두고, 세 용액의 최소 합을 구하려 노력하였다.

-> [index][left][  ] .......[  ][right]

4) 합이 0인 경우, 바로 출력을 진행하였으며 합이 0보다 큰 경우, right를 감소시켰고, 0보다 작은 경우에는 left를 증가 시켰다. 

5) 앞서 정의해 뒀던 최소 값을 기준으로 더 작은 합이 존재할 경우, answer 배열에 새로운 값들을 매번 넣어줌으로서 문제를 해결했다.

 

#include <string>
#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
#include <map>
using namespace std;

int n;
vector<long long> vec;
vector<long long> answer;
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        int a; cin >> a;
        vec.push_back(a);
    }
    sort(vec.begin(), vec.end());

    long long minAns = 123456789123456789;
    for (int i = 0; i < vec.size() - 1; i++)
    {
        int start = i + 1;
        int end = vec.size() - 1;
        while (start < end)
        {
            long long sum = vec[i] + vec[start] + vec[end];//세 개의 합
            if (sum == 0)
            {
                answer.clear();
                answer.push_back(vec[i]); answer.push_back(vec[start]); answer.push_back(vec[end]);
                sort(answer.begin(), answer.end());
                for (int i = 0; i < answer.size(); i++)
                {
                    cout << answer[i] << " ";
                }
                return 0;
            }
            else if (sum > 0)
            {
                if (minAns > abs(sum))
                {
                    minAns = abs(sum);
                    answer.clear();
                    answer.push_back(vec[i]); answer.push_back(vec[start]); answer.push_back(vec[end]);
                }
                end--;
            }
            else
            {
                if (minAns > abs(sum))
                {
                    minAns = abs(sum);
                    answer.clear();
                    answer.push_back(vec[i]); answer.push_back(vec[start]); answer.push_back(vec[end]);
                }
                start++;
            }
        }
    }
    sort(answer.begin(), answer.end());
    for (int i = 0; i < answer.size(); i++)
    {
        cout << answer[i] << " ";
    }
}