(C++) 백준 1026번 - 보물

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

1026번: 보물

문제 풀이

그리디 알고리즘을 활용한 문제이다.

여러 수들의 곱의 최솟값을 구하고 싶다면 최댓값에 최솟값을 곱해주면 되고, 곱의 최댓값을 구하고 싶다면 최댓값끼리 곱해주면 된다. 

그렇기에 우선 오름차순으로 정렬을 진행하고, 한 배열에선 값이 작은 앞의 원소를, 다른 배열에서는 값이 큰 뒤의 원소를 차례대로 곱하면 최솟값을 구할 수 있다.  

#include <iostream>
#include <algorithm>

using namespace std;

int A[55], B[55];
int n, mn;

int main() {
    ios::sync_with_stdio(0);  
    cin.tie(0);
    cout.tie(0);
    
    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);
    for(int i = 0; i < n; i++) mn += A[i] * B[n-i-1];
   
    cout << mn;
}