[레벨 2 ] 최솟값 만들기

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

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

 

 

두 수를 곱하면서 더한 값이 최솟값이 되게 만들어야한다.

 

즉 곱하는 두 수가 최대한 작아야한다는 의미. 서로 작은 수 끼리 곱해서 더해봤자 점점 커지는 수 끼리 곱해지기에 의미가 없다.

 

그렇기에 최대한 큰 수를 가장 작은 수와 매번 곱해주는게 이 문제의 해결방법.

즉

[1, 4, 2]

[5, 4, 4]

라면

[1, 2, 4]

[4, 5, 5]

로 정렬 후 가장 작은 수(맨왼쪽) + 가장 큰 수(가장 오른쪽)를 곱하고 더하면 된다.