문제

옛날 옛적에 수학이 항상 큰 골칫거리였던 나라가 있었다. 이 나라의 국왕 김지민은 다음과 같은 문제를 내고 큰 상금을 걸었다.

길이가 N인 정수 배열 A와 B가 있다. 다음과 같이 함수 S를 정의하자.

S = A[0] * B[0] + … + A[N-1] * B[N-1]

S의 값을 가장 작게 만들기 위해 A의 수를 재배열하자. 단, B에 있는 수는 재배열하면 안된다.

S의 최솟값을 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. 둘째 줄에는 A에 있는 N개의 수가 순서대로 주어지고, 셋째 줄에는 B에 있는 수가 순서대로 주어진다. N은 50보다 작거나 같은 자연수이고, A와 B의 각 원소는 100보다 작거나 같은 음이 아닌 정수이다.

출력

첫째 줄에 S의 최솟값을 출력한다.

예제 입력/출력

코드

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

int main() {
	int n, tmp, min_s = 0;
	vector<int> A, B;

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

	sort(A.begin(), A.end());   // 오름차순 정렬
	sort(B.begin(), B.end(), greater<int>());   // 내림차순 정렬

	for (int i = 0; i < n; i++)
		min_s += A[i] * B[i];

	printf("%d\n", min_s);

	return 0;
}

풀이

간단한 문제이다.
문제에서는 A의 수만 재배치한다고 주어졌다. 그러나 실상 A를 재배치 시키든 A,B 둘다 재배치 시키는 상관이 없다. A를 재배치 하지만, B의 입장에서는 짝이 바뀌었기 때문에 마치 B가 움직인것 처럼 느낄 수 있기 때문이다.

문제에서 요구하는 것은 동일한 ‘열’의 곱셈 값을 다 더했을 때 가장 작은 값이다.
최대한 곱한 값들이 작게 나오기 위해서 작은값 * 큰값으로 매칭시켜야 한다. “작은값 * 작은값” 을 만들면 물론 작게 나오겠지만, 남아있는 값들은 “큰값 * 큰값” 형태를 띄기 때문에 전체 값을 더했을 때 커질 수 밖에 없다.

위의 코드는 A는 오름차순으로, B는 내림차순으로 정렬하여, 각 열의 값을 곱한 다음(작은값 * 큰값) min_s에 더해주는 형식으로 하였다.
이렇게 되면 S의 최소값이 나온다.