백준 1026 보물 [C++]

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

1026번: 보물

 

두 배열이 주어졌을 때 출력될 수 있는 가장 작은 값을 구하기 위해선, 가장 작은 수와 가장 큰 수를 곱하여 그 결과를 더하면 될 것이라 생각했다. 

A	1	2	3
B	4	5	6

다음과 같이 수가 주어졌을 때 A의 가장 큰 요소와 B의 가장 큰 요소를 찾아 곱한 값을 더하면 가장 큰 결과를 얻는다.

(3 x 6) + (2 x 5) + (1 x 4)  = 32

만약 한 쪽 배열의 가장 큰 요소와 다른 배열의 가장 작은 요소를 곱한다면, 문제에서 요구하는 값을 찾을 것 같았다.

(1 x 6) + (2 x 5) + (3 x 4) = 28

---

코드

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

bool compare(int i, int j){
  return j < i;
}

int main(){
  int N, S = 0, num;
  cin >> N;
  vector<int> A,B;

  for(int i = 0; i < N; i++){
    cin >> num;
    A.push_back(num);
  }
  for(int i = 0; i < N; i++){
    cin >> num;
    B.push_back(num);
  }

  sort(A.begin(), A.end());
  sort(B.begin(), B.end(),compare);

  for(int i = 0; i < N; i++){
    S += A[i] * B[i];
  }
  cout << S;
  
}