[백준] 1026번 : 보물 (C++)

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

 

 

 

 

풀이)

배열 하나는 오름차순 나머지 하나는 내림차순으로 정렬 후에

 

위의 식을 적용하면 자연스레 최대한 작은 값이 나오게 된다.

 

따라서 <algorithm> STL의 sort()를 사용하되,

 

내림차순의 경우 compare() 함수를 만들어 내림차순이 나올 수 있도록 했다.

 

#include <iostream>
#include <algorithm>
#include <vector>
 
using namespace std;
 
bool compare(int a, int b) {
    if (a > b) {
        return 1;
    }
    else {
        return 0;
    }
}
 
 
int main()
{
    int n, result = 0;
    vector<int> array1;
    vector<int> array2;
 
    cin >> n;
 
    int a;
    for (int j = 0; j < n; j++) {
        cin >> a;
        array1.push_back(a);
    }
        
    for (int j = 0; j < n; j++) {
        cin >> a;
        array2.push_back(a);
    }
 
    sort(array1.begin(), array1.end());
    sort(array2.begin(), array2.end(), compare);
    
    for (int i = 0; i < n; i++) {
        result += array1[i] * array2[i];
    }
 
    cout << result;
 
    return 0;
}
 

---

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

1026번: 보물