플밍카이브

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

#include <iostream>
#include <vector>
#include <map>
#include <queue>
#include <string>
#include <algorithm>
using namespace std;

int S(int A[], int B[], int N)
{
	int sum = 0;

	for (int i = 0; i < N; i++)
	{
		sum += (A[i] * B[i]);
	}

	return sum;
}


int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);

	int N;
	cin >> N;

	int A[50];
	int B[50];
	
	for (int i = 0; i < N; i++)
		cin >> A[i];

	for (int i = 0; i < N; i++)
		cin >> B[i];

	sort(A, A + N, greater<>());
	sort(B, B + N);

	cout << S(A, B, N);


}

문제

A를 재배열해서 함수 S로 나올 수 있는 최솟값을 구하라

A를 어떻게 재배열해서 재배열하지않은 B를 이용해 최솟값을 구할 수 있을까?

B를 재배열하지말라고 했는데 위 문제는 딱히 재배열해도 답을 구하는데 문제가 생기지 않는다.

어찌됐든 B의 각 원소들은 A의 N개의 임의의 원소들과 곱해질 것이기때문에

A[i] * B[i] 의 최솟값은 뭐가 될 까? 

생각해보면 최댓값은 가장 큰 원소와 가장 큰 원소끼리 곱하면서 더하면 될 것이다.

그러면 최솟값은 가장 큰 원소와 가장 작은 원소끼리 곱해서 더하면 되지 않을까?

나는 A를 내림차순으로 정렬하고 B를 오름차순으로 정렬한 뒤 S함수를 실행시켜서 최솟값을 구해보았다

결과는 정답, 문제에서 재배열 하지말라고 했지만  딱히 문제가 되지 않기 때문에 그냥 정렬을 이용해서 푼 문제