(C++) baekjoon 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의 최솟값을 출력한다.

---

예제 입력 1

5
1 1 1 6 0
2 7 8 3 1

예제 출력 1

18

예제 입력 2

3
1 1 3
10 30 20

예제 출력 2

80

예제 입력 3

9
5 15 100 31 39 0 0 3 26
11 12 13 2 3 4 5 9 1

예제 출력 3

528

힌트

예제 1의 경우 A를 {1, 1, 0, 1, 6}과 같이 재배열하면 된다.

---

<code>

/*
2022_09_19
backjoon 1026 tresure https://www.acmicpc.net/problem/1026
*/
#include<iostream>
#include<algorithm>

using namespace std;

bool desc(int& a, int& b) { //내림차순 정렬
    return a > b;
}

int main(){

    int n;      // 배열의 길이
    int a[50],b[50];    //배열

    cin >> n;
    for(int i=0; i<n; i++){ //n길이만큼의 a배열입력
        cin >> a[i];
    }
    for(int i=0; i<n; i++){ //n길이만큼의 b배열입력
        cin >> b[i];
    }

    sort(a,a+n);        //a,b 오름차순, 내림차순 정렬
    sort(b,b+n,desc);

    int sum = 0;
    for(int i=0; i<n; i++){
        sum += a[i] * b[i];
    }
    cout << sum;
    return 0;
}

---

이문제를 풀때 처음에는 A배열과 B배열을 각각 오름차순, 내림차순으로 정렬하여 곱연산을 해주면 쉽게 구할 수 있겠다는 생각이 들었지만 문제에 정의되어있는 "B에 있는 수는 재 배열 하면 안된다" 라는 문구를 보고 쉽게 생각이 떠오르지 않았지만 한 Q&A의 답변을 보니 

   - 예를 들어 이 문제의 출제 의도에는 "A만 재배열할 때의 답을 구하는 것이 A와 B를 둘 다 재배열할 때의 답을 구하는 것과 동치임을 알아낼 수 있는가"를 시험하는 것이 포함되어 있습니다. 그걸 알아내야 이 문제를 쉽게 풀 수 있고, 실제로 문제를 풀 때 A와 B를 어떻게 처리하든지 그 과정은 완전히 프로그래머의 자유입니다. 출력한 답이 "A만 재배열할 때의 답"과 같기만 하면 됩니다.

라는 문구를 보고 해결할 수 있는 다양한 경우의 수를 생각해내는 것이 중요하다는 생각을 했다. 물론 B를 재배열 한 값과 재배열 하지 않은 값이 충분히 같을것이라고 판단 후 처음 생각해낸대로 문제를 풀어 나갔다.

어렵지 않게 A는 오름차순, B는 내림차순 정렬을 통해 각각의 첫번째 인덱스 부터 마지막 까지 곱연산을 해주어 해결했다.