[C++] BaekJoon / 1026번 / 보물

- 문제

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

길이가 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의 최솟값을 출력한다.

5
1 1 1 6 0
2 7 8 3 1

18

---

#include <iostream>

using namespace std;

void quickSort(int* _A, int _left, int _right)
{
	int pl = _left;
	int pr = _right;
	int pivot = _A[(_left + _right) / 2];

	while (pl <= pr)
	{
		while (_A[pl] < pivot) ++pl;
		while (_A[pr] > pivot) --pr;

		if (pl <= pr)
		{
			int temp = _A[pl];
			_A[pl] = _A[pr];
			_A[pr] = temp;

			++pl;
			--pr;
		}
	}

	if (_left < pr) quickSort(_A, _left, pr);
	if (pl < _right) quickSort(_A, pl, _right);
}

int S(int* _A, int* _B, int _N)
{
	quickSort(_A, 0, _N - 1);	// 배열 A 오름차순 정렬

	int sum = 0;

	// 계산 완료된 요소의 상태를 나타내기 위한 배열(0 or 1)
	int* check = new int[_N] {};

	for (int i = 0; i < _N; ++i)
	{
		int max = 0;
		int maxIndex = 0;
		for (int j = 0; j < _N; ++j)
		{
			if (max < _B[j] && check[j] == 0)
			{
				max = _B[j];
				maxIndex = j;
			}
		}

		check[maxIndex] = 1;
		sum += _A[i] * max;
	}

	delete[] check;

	return sum;
}

int main()
{
	int N;
	cin >> N;

	int* A = new int[N];
	int* B = new int[N];
	
	for (int i = 0; i < N; ++i)
		cin >> A[i];
	for (int i = 0; i < N; ++i)
		cin >> B[i];

	cout << S(A, B, N);
}