[백준/Baekjoon] 2473 세 용액 C++ :: Two pointer

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

2473번: 세 용액

---

1. Logic

기초적인 Tow pointer 문제지만 여기선 세개의 용액을 구해야하기 때문에 아이디어가 필요하다. 문제를 처음 보고 떠오른 아이디어는 한용액은 고정으로 하고 나머지 두개만 고르면 되겠다! 이거였다. 그리고 내가 생각한 아이디어가 맞았다.

 

기본 로직을 적어보자면

1. 0번째 인덱스부터 n - 2번째 인덱스 까지 for문을 돌면서 고정할 용액을 정한다.

2. 남은 두개용액을 투포인터를 활용하여 선정하며 3개를 더한 값이 이전의 sum값보다 0에 가까우면 갱신해준다.

    >> 0에 가까운지를 판단하는 방법은 둘다 절대값을 씌웠을 때 더 작은게 0에 가까운것이다.

 

---

2. Code

#include<bits/stdc++.h>

using namespace std;

vector<long long> input;
vector<long long> ans(3, 0);
long long res = LLONG_MAX;

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

    int n; 
    cin >> n;

    for(int i = 0; i < n; i++) {
        int a;
        cin >> a;
        input.push_back(a);
    }

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

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

        while(left < right) {
            long long val = input[i] + input[left] + input[right];

            if(abs(val) < res) {
                ans[0] = input[i];
                ans[1] = input[left];
                ans[2] = input[right];
                res = abs(val);
            }

            if(val < 0) {
                left++;
            }
            else {
                right--;
            }
        }
    }

    for(int i = 0; i < 3; i++) {
        cout << ans[i] << " ";
    }
}

---

3. Feedback

아이디어 싸움이었는데 비교적 짧은 시간안에 아이디어가 떠올라서 다행이었다.

알고리즘 Solve 후 제가 생각한 Logic을 기록하는 개인 공부 블로그입니다.
내용 중 최적화가 가능한 부분등은 언제든지 댓글로 틀린 부분 및 피드백 주시면 공부 및 반영하겠습니다🧐