문제

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

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

S = A[0] × B[0] + ... + A[N-1] × B[N-1]

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

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

입력

• 첫째 줄: N (N ≤ 50)
• 둘째 줄: A에 있는 N개의 수
• 셋째 줄: B에 있는 N개의 수
  • 0 < 각 원소 ≤ 100

5
1 1 1 6 0
2 7 8 3 1

출력

S의 최소값을 출력한다.

18

문제 풀이

A[i] * B[i] 의 총합을 최소로 만들기 위해서, B의 값이 클 수록 A의 작은 값이 곱해져야 합니다. (이 부분이 그리디 알고리즘입니다. 매 순간 A의 가장 작은 값을 B의 가장 큰 값 위치에 배치하는 겁니다.)

A배열은 오름차순으로, B배열은 내림차순으로 하여 순서대로 곱하면 쉽겠지만, 문제에서는 B배열의 순서는 바꿀 수 없다고 합니다. 따라서 정렬 대신 인덱스를 사용해 재배치 합니다.

우선, A배열을 오름차순으로 정렬합니다.

const arrA = input[1].split(' ').map(Number).sort((a, b) => a - b);

그 다음, B배열을 인덱스를 함께 저장하는 새로운 배열을 만들어서 내림차순으로 정렬합니다.

const arrB = input[2].split(' ').map(Number);
const indexB = arrB.map((val, idx) => ({val, idx})).sort((a, b) => b.val - a.val);

이렇게 하면 indexB배열은 다음과 같이 생겼습니다.

const indexB = [
	{val: 8, idx: 2},
	{val: 7, idx: 1},
	{val: 3, idx: 3},
	{val: 2, idx: 0},
	{val: 1, idx: 4}
]

이 배열의 idx 값을 가지고 arrA 배열을 정렬합니다.

const newA = [];
for (let i = 0; i < N; i++) {
  newA[indexB[i].idx] = arrA[i];
}