BOJ 1026번 보물

BOJ : https://www.acmicpc.net/problem/1026

github : https://github.com/junho0956/Algorithm/blob/master/1026/1026/%EC%86%8C%EC%8A%A4.cpp

 

문제의 조건에 A와 B 배열의 값은 음이아닌 정수라고 하였다.

그러므로 두 배열의 각 인자들의 곱에 대한 합이 최소가 되기 위해서는

큰수는 작은수, 작은수는 큰수와 곱해주면 된다.

배열하나는 오름차순, 나머지 하나는 내림차순으로 정렬 후 곱해주면 된다 

 

#include <iostream>
#include <algorithm>
using namespace std;
 
int A[51], B[51];
bool cmp(int& a, int& b) {
    return a > b;
}
int main() {
    int N; cin >> N;
    for (int i = 0; i < N; i++) cin >> A[i];
    for (int i = 0; i < N; i++) cin >> B[i];
    sort(A, A + N, cmp);
    sort(B, B + N);
    int ans = 0;
    for (int i = 0; i < N; i++) ans += (A[i] * B[i]);
    cout << ans;
    return 0;
}