[백준/C++] #2467 용액 (Two Pointer)

문제

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

 

 

 

알고리즘

: two pointer

 

풀이 + 코드

가장 기초적인 투포인터 문제다.

(정렬된) 용액 특성들을 배열에 넣고, 두개의 포인터를 이용하여 배열 값들의 합을 구하며 0과 가장 가까운 값이 나타나면 답을 갱신한다.  

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#define MAX 100001
#define INF 987654321
#define endl "\n"
using namespace std;
/*
2467번 용액
산성 용액: 1부터 1,000,000,000, 알칼리성 용액: -1부터 -1,000,000,000
같은 양의 두 용액을 혼합한 용액의 특성값은 혼합에 사용된 각 용액의 특성값의 합
같은 양의 두 용액을 혼합하여 특성값이 0에 가장 가까운 용액을 만들려고 함. 두 용액 찾자. 

용액 수는 2~100000
*/

int n;
vector<int> liquids(MAX);

void solution() {
    int left_idx = 0;
    int right_idx = n - 1;

    int ans = abs(liquids[left_idx] + liquids[right_idx]);
    int ans_left = left_idx;
    int ans_right = right_idx;

    while (left_idx < right_idx) { // left_idx와 right_idx는 만나면 안된다
        int tmp = liquids[left_idx] + liquids[right_idx];

        if (abs(tmp) < ans) { // 갱신
            ans_left = left_idx;
            ans_right = right_idx;
            ans = abs(tmp);

            if (ans == 0) {
                break;
            }
        }

        if (tmp < 0) { // 작으면 키우고
            left_idx++;
        }
        else { // 크면 줄이고
            right_idx--;
        }
    }

    // 출력
    cout << liquids[ans_left] << " " << liquids[ans_right] << endl;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    // 입력
    cin >> n;
    liquids.resize(n);

    // 무조건 오름차순으로 입력된다.
    for (int i = 0; i < n; ++i) {
        cin >> liquids[i];
    }

    // 로직
    solution();

    return 0;
}