1026)보물

https://www.acmicpc.net/problem/1026

이 문제를 요약해보면 S+=A[i]*B[i]를 구하는 것인데 S가 최소가 되게 해야 한다.

문제를 읽어 보면 함정이 있는데 A는 재배열해도 되고 B는 재배열하지 말라고 한다.

이 문구를 고려하지 않고 수열 A와 수열 B를 최소가 되게 각 항들을 매칭시키는 방법은

A를 오름 차순으로 정렬하고 B를 내림 차순으로 정렬해 A[i]와 B[i]를 매칭시키는 것이다.

왜냐하면 수열 A의 i번째로 큰 값과 수열 B의 i번째로 작은 값을 매칭하기 때문이다.

그래서 두 항 A[i]와 B[i]의 곱은 항상 i번째로 작을 수 밖에 없다.

#include<stdio.h>
 
void swap(int *A, int *B) {
    int temp;
 
    temp = *A;
    *A = *B;
    *B = temp;
}
 
int partition(int *A, int p, int r) {
    int pivot = (p + r) / 2;
    int i = p - 1;
 
    swap(&A[pivot], &A[r]);
    for (int j = p; j < r; j++) {
        if (A[j] < A[r]) {
            swap(&A[++i], &A[j]);
        }
 
    }
    swap(&A[i + 1], &A[r]);
 
    return i + 1;
}
 
void quickSort(int *A, int p, int r) {
    int q;
 
    if (p < r) {
        q = partition(A, p, r);
        quickSort(A, p, q - 1);
        quickSort(A, q + 1, r);
    }
}
 
int main() {
    int *A;
    int *B;
    int N;
    int sum = 0;
 
    scanf("%d", &N);
    A = (int *)malloc(sizeof(int)*N);
    B = (int *)malloc(sizeof(int)*N);
 
    for (int i = 0; i < N; i++) {
        scanf("%d", &A[i]);
    }
    for (int i = 0; i < N; i++) {
        scanf("%d", &B[i]);
    }
 
    quickSort(A, 0, N - 1);
    quickSort(B, 0, N - 1);
 
    for (int i = 0; i < N;i++) {
        sum += A[i] * B[(N - 1) - i];
    }
 
    printf("%d\n",sum);
 
    return 0;
}