백준 2467번 용액 (C++)

문제 링크 : https://www.acmicpc.net/problem/2467

2467번: 용액

문제 요약

 

1.  -1,000,000,000 부터 1,000,000,000 까지의 특성값을 지닌 산성 용액 / 알칼리성 용액이 N개 주어집니다.

2. 특성값은 알칼리성(음수)부터 산성(양수)까지 오름차순으로 주어집니다.

3. 서로 다른 두 용액을 혼합하여 특성값이 0에 가장 가까운 용액을 만들어내는 두 용액을 찾아 입력하세요.

4. 답이 여러가지 일 경우 아무 답이나 출력하세세요.

 

핵심 포인트

오름차순으로 값이 주어지기 때문에 정렬을 할 필요가 없습니다.

이분 탐색(투 포인터)으로 쉽게 접근할 수 있는 문제입니다.

 

문제 풀이

 

1. n과 필요한 값들을 입력 받습니다.

int left=0,right=0,n=0, sum = 2000000000, temp = 0; 
// sum : 가장 0에 가까운 두 용액의 핪, temp : 두 용액의 임시 저장값
    cin >> n;
    vector<int> v(n);
    for(int i=0; i<n; i++) cin >> v[i];

이때 sum의 값은 가장 크게 나올 수 있는 두 수의 합의 절대값으로 초기화 합니다.

 

2. 이분 탐색을 진행합니다. 

    int le=0, ri=n-1;
    while(le<ri){
        temp = v[le]+v[ri]; // 1 현재 투 포인터가 가르키는 용액들의 합
        if(abs(sum)>abs(temp)){ // 2 만약 sum의 절대값이 temp의 절대값보다 크다면, temp가 0에 더 가깝다는 뜻
            left = v[le]; // 3
            right = v[ri]; 
            sum = temp;
        }
        if(temp>0) ri--; // 4
        else le++; // 5
    }

(1) 현재 투 포인터가 가르키는 용액들의 합
(2) 만약 sum의 절대값이 temp의 절대값보다 크다면, temp가 0에 더 가깝다는 뜻 입니다.

(3) 이때 left와 right, sum의 값을 새로 갱신해줍니다.

(4) 만약 temp의 값이 0보다 크다면 더 작은 양수값을 대입해야 한다는 의미이므로, ri를 -1해줍니다.

(5) 반대의 경우 더 작은 음수의 값을 대입해야 한다는 의미이므로, le를 +1해줍니다.

 

3. 정답을 출력합니다.

cout << left << " " << right << "\n";

 

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int left=0,right=0,n=0, sum = 2000000000, temp = 0;
    cin >> n;
    vector<int> v(n);
    for(int i=0; i<n; i++) cin >> v[i];
    int le=0, ri=n-1;
    while(le<ri){
        temp = v[le]+v[ri];
        if(abs(sum)>abs(temp)){
            left = v[le];
            right = v[ri];
            sum = temp;
        }
        if(temp>0) ri--;
        else le++;
    }
    cout << left << " " << right << "\n";
    return 0;
}