- 문제
옛날 옛적에 수학이 항상 큰 골칫거리였던 나라가 있었다. 이 나라의 국왕 김지민은 다음과 같은 문제를 내고 큰 상금을 걸었다.
길이가 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<자료형>() => 오름차순 을 넣어주면 된다.
sort함수 부분에서 N^2또는 NlogN이 나올 것이기에 Big-O 표기법 정의에 의해 N^2으로 표시했다.