백준 1026번 : 보물

재귀로 직접 낮은 값을 찾아가는 것은 시간이 너무 오래걸린다. 단순히 큰 값에는 작은 값을 곱해야 작은 수를 얻을 수 있다는 점에 착안해 A는 오름차순, B는 내림차순 정렬 후 값을 구하는 것이 훨씬 빠르다.

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int main()
{
	int N;
	scanf("%d", &N);

	vector<int> A, B;
	for (int i = 0; i < N; i++)
	{
		int n;
		scanf("%d", &n);
		A.push_back(n);
	}
	for (int i = 0; i < N; i++)
	{
		int n;
		scanf("%d", &n);
		B.push_back(n);
	}

	sort(A.begin(), A.end());
	sort(B.begin(), B.end(), greater<int>());
	int S = 0;
	for (int i = 0; i < N; i++)
	{
		S += A[i] * B[i];
	}

	printf("%d", S);
	return 0;
}