[백준][C++] 2470 두 용액

www.acmicpc.net/problem/2470

2470번: 두 용액

 

 

 

알고리즘 종류

    - 투 포인터

 

 

 

사고 과정

    - 두 개의 포인터를 배열의 양끝에 놓고 비교하면서 포인터를 움직이면 된다.

        1. left와 right에 해당하는 값을 더해서 sum을 구한다.

        2. sum의 절대값이 이전의 값보다 작으면, left와 right가 가리키는 값을 저장한다.

        3. left와 right가 교차할 때까지 반복한다.

 

 

 

구현(C++)

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
 
using namespace std;
 
int n;
vector<long long> v;
 
int main(void){
    
    cin >> n;
    
    v.resize(n, 0);
    for(int i=0; i<n; i++) cin >> v[i];
    
    sort(v.begin(), v.end());
    
    int left=0, right=n-1;
    long long sum, answer=9987654321;
    long long liquid_1, liquid_2;
    
    while(left < right){
        
        sum = v[left] + v[right];
 
        if(abs(sum) < answer){
            answer = abs(sum);
            liquid_1 = v[left];
            liquid_2 = v[right];
            
        }
        
        if(sum <= 0) left++;
        else if(sum > 0) right--;
    }
 
    cout << liquid_1 << " " << liquid_2 << "\n";
}

 

 

 

시행착오

    - 이분탐색으로 풀어볼려고 했다. 왜냐하면, 투 포인터로 풀 수 없을 것 같았기 때문이다. 지금까지 풀어온 투 포인터의 문제는 왼쪽에서 left와 right가 출발하는 유형이었다. 그런데 여기서는 left 포이터를 왼쪽에두고, right 포인터를 오른쪽에 두어서 수행하면 된다. 투 포인터의 유형을 하나 더 배우게 되었다.