[백준] 1026 보물 with C++

문제설명

---

입출력 예제

---

개념

　배열 A와 B를 받아, 두 배열의 곱의 합 A[i] * B[i]의 합의 최솟값을 구하는 문제다. 이는 A 배열의 최솟값과 B 배열의 최댓값을 곱하면 쉽게 해결할 수 있다. 이를 엄밀히 증명하면 다음과 같다.

 

a ≤ b 그리고 c ≤ d를 가정하면 (여기서 a, b, c, d는 임의의 실수입니다), 이때 다음 부등식이 성립한다

ac + bd ≤ ad + bc

 

이 부등식은 다음과 같이 변환된다.

ac + bd - ad - bc ≤ 0
=> ac - ad + bd - bc ≤ 0
=> a(c - d) + b(d - c) ≤ 0
=> (a - b)(c - d) ≤ 0

이제 우리가 얻은 부등식에 두 배열의 원소들을 대입해보자. 배열 A와 B가 주어지고, A의 원소 a, b (a ≤ b)와 B의 원소 c, d (c ≤ d)가 주어진다. 우리는 a와 d의 조합이 b와 c의 조합보다 크다고 가정하면, 위의 부등식이 성립한다는 것을 알 수 있다. 그러나 이는 원래의 가정과 모순되므로, a와 d의 조합이 b와 c의 조합보다 작거나 같아야 한다.

---

풀이

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main()
{
    int N, sum = 0;
    cin >> N;

    vector<int> v1(N), v2(N);

    for (int i = 0; i < N; ++i)
        cin >> v1[i];

    for (int i = 0; i < N; ++i)
        cin >> v2[i];

    sort(v1.begin(), v1.end());
    sort(v2.rbegin(), v2.rend());

    for (int i = 0; i < N; ++i)
        sum += v1[i] * v2[i];

    cout << sum;
}