[C++][백준 1026] 보물

문제

접근 방법

B에 있는 수는 재배열하면 안 된다고 적혀있기에 건들면 안 될 것 같은 느낌이 든다.
하지만 더하기의 경우 순서가 상관없기에 두 배열 모두 정렬해도 된다.

코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> A, B;
int main()
{
    ios::sync_with_stdio(0), cin.tie(0);
    int N, ret = 0;
    cin >> N;
    A = B = vector<int>(N);
    for (int i = 0; i < N; ++i)
    {
        cin >> A[i];
    }
    for (int i = 0; i < N; ++i)
    {
        cin >> B[i];
    }

    sort(A.begin(), A.end());
    sort(B.begin(), B.end(), greater<int>());
    for (int i = 0; i < N; ++i)
    {
        ret += A[i] * B[i]; // 큰 값 * 작은 값
    }
    cout << ret;
    return 0;
}

풀이

문제의 제약이 풀이의 제약이 될 수 없다는 것을 알 수 있다.
오름차 순, 내림차 순으로 정렬하여 곱하면 가장 작은 S의 값을 구할 수 있다.