[백준] 1026번 보물

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

---

풀이)

처음에 아무 생각 없이 배열 a가 나올 수 있는 모든 순열을 구했다가 시간초과를 겪은 문제이다.

어떤 정렬을 하든 단순히 a배열과 b배열 곱의 최솟값만 구하면 되는 것이니,

a배열을 오름차순, b배열을 내림차순해서 곱하면 되는 쉬운 문제였다.

코드)

#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
 
int n;
vector <int> a, b;
long long result = 0;
 
bool desc(int a, int b) {
    return a > b;
}
 
int main() {
    scanf("%d", &n);
    a.resize(n);
    b.resize(n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
    }
    for (int i = 0; i < n; i++) {
        scanf("%d", &b[i]);
    }
    sort(a.begin(), a.end());
    sort(b.begin(), b.end(), desc);
    for (int i = 0; i < n; i++) {
        result += a[i] * b[i];
    }
    printf("%lld", result);
    return 0;
}