[프로그래머스] 최솟값 만들기

두 배열의 원소를 하나씩 곱하여 더했을때 최소인 값을 만들어내야 한다.
완전 탐색으로 수행하면 O(N!)이 소요되고 (1$\leq$ N $\leq$ 1000) 이므로 불가능하다.

직관적으로 큰 수를 작은수들과 우선적으로 곱했을 때 결과가 더 작아진다는 걸 알 수 있으므로 탐욕법을 이용하여 해결한다.

https://school.programmers.co.kr/learn/courses/30/lessons/12941

cpp code

#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(), less<int>());
    sort(B.begin(), B.end(), greater<int>());
    
    for (int i=0;i<A.size();i++) {
        answer += A[i] * B[i];
    }

    return answer;
}