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

#include<iostream>
#include<algorithm>
using namespace std;
int N, sum;
int A[51];
int B[51];

void fast_io()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
}
void fill_array(int* arr)
{
	for (int i = 0; i < N; i++)
	{
		int num; cin >> num;
		arr[i] = num;
	}
}

bool compare(int x, int y)
{
	return x > y;
}
int main()
{
	fast_io();
	cin >> N;
	fill_array(A);
	sort(A, A + N);
	fill_array(B);
	sort(B, B + N, compare);
	for (int i = 0; i < N; i++)
	{
		sum += A[i] * B[i];
	}
	cout << sum;
	return 0;
}

  문제에서는 B 배열을 건드리면 안된다고 했으나 최솟값만 출력하면 되기 때문에 정렬을 해도 상관없다.
최솟값은 (A의 최소 * B의 최대) 묶음으로 더해가면 되기 때문에 A배열은 오름차순, B배열은 내림차순으로 정렬 후 sum값을 구하였다.

sort함수에서 오름차순, 내림차순 정렬하는 방법은 3번째 인자로 compare함수를 직접 만들어서 전달해주거나 geater<자료형>() => 내림차순, less<자료형>() => 오름차순 을 넣어주면 된다.

시간 복잡도 : O(N^2)

sort함수 부분에서 N^2또는 NlogN이 나올 것이기에 Big-O 표기법 정의에 의해 N^2으로 표시했다.