[백준] 1026번 보물

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

1026번: 보물

1. 문제 접근

S = A[0]×B[0] + ... + A[N-1]×B[N-1] 식에서 +연산은 교환법칙이 성립하기에 A배열이 재배치가 가능하다는 소리는 B배열 또한 재배치가 가능한 상황과 동일하며 순서에는 재약이 없다는 의미이다. 그렇다면 가장작은 S값을 구하기 위해 A와 B를 어떻게 재배치할지 고민해 보자.

 

우선 A[0]×B[0], A[1]×B[1], ..., A[N-1]×B[N-1] 각각의 값들이 작아야한다. B배열에서 S값에 가장 크게 영향을 줄 값은 B배열이 가진 값들 중 가장 큰 값이며 따라서 이 값을 먼저 고려해보면 A배열에서 가장 작은 값과 곱해져야만 가장 작은 값이 나오게 된다. 마찬가지로 다음으로 고려할 값은 두번째로 S값에 크게 영향을 미칠 값이며 이는 B배열의 값들 중 두번째로 큰 값일테고 A배열에서 두번째로 작은 값과 곱해져야 한다. 이런방식으로 B배열이 끝날때까지 진행하면 가장 작은 S값을 얻을 수 있을 것이다.

 

이를 위해 B배열을 내림차순(3,2,1)으로 정렬시키고 A배열을 오름차순(1,2,3)으로 정렬시켜 같은 인텍스값을 가지는 값들끼리 곱한뒤 그들의 합을 S로 두면 답이 될 것이다.

 

시간복잡도 계산

A, B배열을 정렬하는 연산과, 같은 인덱싱값들끼리 곱하여 더하는 연산을 고려해보면 아래와 같이 시간복잡도를 계산할 수 있다. 이때 N의 최댓값은 고작 50이라고 하였으니 굳이 횟수로 계산해보면 5050번이 되고 이는 주어진 시간 2초를 고려하였을때 차고 넘치는 횟수 이다. 따라서 굳이 시간복잡도가 더 좋은 정렬연산방법도 고려할 필요가 없어 보인다.

시간복잡도 = O(N^2) + O(N^2) + O(N) ≒ 5050

 

 

 

2. 코드

#include<iostream>
using namespace std;

#define MAX_N 50

int descend(int a, int b) {
    return a - b;
}

int ascend(int a, int b) {
    return b - a;
}

void insertSort(int arr[], int arrLen, int(*compare)(int, int)) {
    for (int i = 0; i < arrLen; i++) {
        int maxIdx = i;
        for (int j = i; j < arrLen; j++) {
            if (compare(arr[maxIdx], arr[j]) < 0)
                maxIdx = j;
        }
        int temp = arr[maxIdx];
        arr[maxIdx] = arr[i];
        arr[i] = temp;
    }
}

int main() {
    int N;
    int A[MAX_N];
    int B[MAX_N];
    int answer = 0;

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

    insertSort(A, N, ascend);       // A 오름차순
    insertSort(B, N, descend);      // B 내림차순

    for (int i = 0; i < N; i++)
        answer += (A[i] * B[i]);    // 같은 인덱스 값끼리 곱한뒤 이들을 모두 더한다

    cout << answer << endl;

    return 0;
}