[PS] 최솟값 만들기

문제

해결

두 수를 곱한 값의 누적이 최소가 되도록 만드는게 목적이니까 두 배열을 정렬해서 a번째와 배열의 길이인 len - a - 1 번째 요소를 곱해서 값을 누적하면 된다.

직관적으로는 큰 수 끼리 곱하면 값이 크게 부풀기 때문에, 큰 수는 작은 수와 묶어 눌러줘야 한다는거고

논리적으로 설명해보면,

A에서 두 수 a1 < a2를, B에서 두 수 b1 < b2를 골랐다고 하자. 짝을 짓는 방법은 두 가지뿐이다.

• 같은 방향(작은 수끼리, 큰 수끼리): a1·b1 + a2·b2
• 엇갈린 방향(작은 수와 큰 수): a1·b2 + a2·b1

두 값을 빼면 이렇게 정리된다.

(a1·b1 + a2·b2) − (a1·b2 + a2·b1) = (a2 − a1)(b2 − b1)

a2 − a1도 양수이고 b2 − b1도 양수이니 결과는 0 이상이다. 즉 엇갈려 짝지으면 합이 절대 커지지 않는다.

어떤 짝 배치든, 작은 A가 작은 B와, 큰 A가 큰 B와 짝지어진 쌍이 하나라도 있다고 하자.
그 두 쌍의 B끼리 자리를 바꾸면 합이 줄거나 그대로다. 위 식이 보장한다.
이 교환을 계속하면 결국 A가 커질수록 B는 작아지는 배치에 도달한다. 매번 뒤집힌 쌍이 하나씩 줄어들기 때문에 교환은 반드시 끝난다.

코드

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

int solution(vector<int> A, vector<int> B)
{
    int answer = 0;
    int len = A.size();
    sort(A.begin(), A.end());
    sort(B.begin(), B.end());
    for(int a = 0; a < len; ++a)
    {
        answer += A[a] * B[len - a - 1];
    }

    return answer;
}