[백준] 2467번 용액

문제: 2467번: 용액

basic-algo-lecture/workbook/0x13.md at master · encrypted-def/basic-algo-lecture

basic-algo-lecture/workbook/0x13.md at master · encrypted-def/basic-algo-lecture

 

#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>
#include <cmath>
#include <limits>
#include <string>

using namespace std;

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

    int n;
    cin >> n;
    vector<long long> solutions(n);
    for (int i = 0; i < n; i++)
        cin >> solutions[i];

    int st = 0;
    int en = n - 1;
    long long ans1 = 2147483647;
    long long ans2 = 2147483647;
    while (st < en) {
        if (abs(ans1 + ans2) > abs(solutions[st] + solutions[en])) {
            ans1 = solutions[st];
            ans2 = solutions[en];
        }
        if (abs(solutions[st] + solutions[en - 1]) <= abs(solutions[st + 1] + solutions[en]))
            en--;
        else
            st++;
    }
    cout << ans1 << " " << ans2;

    return 0;
}

 

음.. 나는 아무리 생각해도 투포인터 방법밖에 모르겠는데 이분 탐색으로 푸는 방법도 있었다. for 문 돌면서 해당 요소랑 같이 더했을 때 0에 가까운 애를 이분탐색으로 찾아주면 된다고 한다..

 

 

 

참고자료:

[이분 탐색,투포인터/파이썬] 백준 2467번 용액

[이분 탐색,투포인터/파이썬] 백준 2467번 용액