[BOJ] 백준 2470 두 용액

출처: https://www.acmicpc.net/problem/2470

 Input 

5

-2 4 -99 -1 98

 

 Output 

-99 98

※ 같은 문제 다른 풀이: [Jungol] 2306 두 용액 

[Jungol] 정올 2306 두 용액

 

가장 가까운 두 수의 합이 0에 가장 가까운 두 수를 구하는 것입니다.

* 양수만 주어지거나 음수만 주어질 수도 있다

 

부호를 고려하지 않기 위해 절대값 기준으로 숫자들을 저장

(부호는 pair를 이용해서 같이 저장)

arr = { -99, -4, 1, -2, 98 }

vector = {(1, 1), (2, -1), (4, -1), (98, 1), (99, -1)}

              → {1, -2, -4, 98, 99} 

그 후 인접한 두 수 합을 구한 해서 0에 가장 가까운 두 수를 찾습니다.(갱신)

ex) 1 - 2 / -2 - 4 / -4 + 98 / 98 + 99

 

Q. 절대값 기준으로 정렬한 후, 왜 인접한 두 숫자만 비교하면 될까?

정렬된 세 개의 숫자가 존재한다고 A, B, C 했을 때,

인접하지 않은 두 수의 합 A + C 와 인접한 두 수의 합 A + B or B + C 

① 부호가 모든 같은 경우: [- - -], [+ + +]

    → 어떤 숫자이든 |A + C| > |A + B| 로 A+C가 0과 더 멀리 떨어져 있는것을 확인

② A와 C가 같은 부호이면서 B만 다른 부호 [+ - +], [- + -]

    → |A + C| 보다 |A + B| or |B + C|가 0하고 가깝습니다.

③ A와 C의 부호가 다른 경우 [- + +], [- - +], [+ + -], [+ - -]

    → [- + +]: |A + B| < |A + C|

    → [- - +]: |B + C| < |A + C|

    → [+ + -]: |B + C| < |A + C|

    → [+ - -]: |A + B| < |A + C|

▶ |A + C| > |A + B| or |B + C| 로서, 절대값 기준으로 정렬한 후 인접한 두 수만 비교하면 됩니다.

---

* 최대 10억의 수를 표현하기 위해 long long 사용

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
#define MAX 2000000001
typedef long long ll;
vector<pair<ll, int> > vec;
 
int main() {
    int N;
    ll firstAns, secondAns, num, sum = MAX;
 
    scanf("%d", &N);
    while (N--) {
        scanf("%lld", &num);
        if (num > 0)
            // 양수
            vec.push_back({num, 1}); 
        else
            // 음수
            vec.push_back({num * -1, -1}); 
    }
 
    sort(vec.begin(), vec.end());
       // arr = {-99 -2 4 -1 98}
    
    // [절대값]: 1  2  4 98 99
    // [부호]:   -  -  +  +  -
    ll temp;
    for (int i = 1; i < vec.size(); i++) {
        temp = vec[i].first * vec[i].second 
            + vec[i - 1].first * vec[i - 1].second;
 
        if (temp < 0)
            temp *= -1;
        if (sum < 0)
            sum *= -1;
 
        if (temp < sum) {
            firstAns = vec[i].first * vec[i].second;
            secondAns = vec[i - 1].first * vec[i - 1].second;
            sum = temp;
        }
    }
 
    if (firstAns <= secondAns) printf("%lld %lld", firstAns, secondAns);
    else printf("%lld %lld", secondAns, firstAns);
}