상식적? 감으로 생각했을 때 S의 값을 가장 적게 만들기 위해서는 제일 작은 수를 제일 큰 수끼리 짝지어서 곱해주었을 때 그 합이 최소가 됩니다. 문제에서 B의 수는 재배열하면 안되지만 A는 옮길 수 있습니다. 이 말은 자칫 B를 고정하고 A를 한 칸씩 옮기는 brute force를 생각할 수 있으나 A,B 둘다 옮길 때와 A의 원소들만을 옆으로 옮겨줄 때는 같다는 생각을 한다면 B를 고정시킬 필요가 없다는 결론에 도달할 수 있습니다.
이 부분은 수학적으로 명확한 검증을 실패했습니다.. 혹시 아시는 분은 댓글로 설명 부탁드립니다...
Code
#include <bits/stdc++.h>
using namespace std;
int a[51],b[51],n,ans;
int main(){
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++){
ans += a[i] * b[n-i-1];
}
cout << ans << '\n';
}