[백준 1026번] 보물

문제 링크: https://www.acmicpc.net/problem/1026

1026번: 보물

<문제 풀이> 그리디

S의 최솟값을 구하는 방법은 배열의 각 원소를 하나씩 꺼낼 때 가장 작은 수와 가장 큰 수를 꺼내서 곱하면 됩니다. 

-> A 오름차순 정렬, B 내림차순 정렬

-> 문제에서 B를 재배치할 수 없다고 했지만 A를 재배치해서 B에 매핑시키는 것이므로 B를 정렬해도 상관없다.

 

<C++ 소스 코드>

#include<iostream>
#include<algorithm>
using namespace std;
 
int N;
 
int A[100], B[100];
 
bool cmp(int& a, int& b) {
    return a > b;
}
 
int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    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);
    sort(B, B + N, cmp);
    int res = 0;
    for (int i = 0; i < N; i++) res += A[i] * B[i];
    cout << res;
    return 0;
}