[C++] 백준 1026번 보물

문제 링크

1026번: 보물

문제 요약

50 이하의 자연수 N이 주어진다. 그 다음에 100 이하의 음이 아닌 정수 N개를 원소로 가진 배열 A와 B가 주어질때, A의 원소를 재배열해서 $\sum\limits_{i = 0}^{N - 1}(A_i\times B_i)$의 결과를 최대로 만들어야 한다.

접근 방법

만약 음수가 포함되어 있었다면 조금 더 생각할 여지가 있었겠지만 이 문제는 입력으로 음수가 들어오지는 않습니다. 그렇기 때문에 각 배열에서 가능한 한 큰 수끼리 묶어서 곱해주면 된다는 것을 간단하게 생각해 낼 수 있습니다.

코드

#include <bits/stdc++.h>

using namespace std;

int main(void)
{
	int n;
	cin >> n;

	vector<int> a(n), b(n);
	for (int i = 0; i < n; i++)
		cin >> a[i];
	for (int i = 0; i < n; i++)
		cin >> b[i];

	sort(a.begin(), a.end(), greater<>());
	sort(b.begin(), b.end());

	int sum = 0;
	for (int i = 0; i < n; i++)
		sum += a[i] * b[i];

	cout << sum << '\n';
	return 0;
}