[백준 1026] 보물 (C#, C++) - soo:bak

문제 링크

1026번 - 보물

설명

두 개의 정수 수열에서 각 원소를 곱한 합이 최소가 되도록 만드는 문제입니다.

• 두 수열의 길이는 동일하며, 각각 정수로 구성되어 있습니다.
  
• 각 위치에서의 곱을 더한 값, 즉
  \(\sum_{i=0}^{n-1} A_i \times B_i\)
  의 결과가 최소가 되도록 수열을 재배열해야 합니다.
  
• 수열 $A$는 순서를 바꿀 수 없고, 수열 $B$만 재배열이 가능합니다.
  

접근법

• 곱의 총합을 최소로 만들기 위해서는, 수열 $A$의 작은 수에 수열 $B$의 큰 수를 곱해야 합니다.
  
• 따라서 수열 $A$는 오름차순으로 정렬하고, 수열 $B$는 내림차순으로 정렬합니다.
  
• 두 수열을 앞에서부터 순서대로 곱한 뒤, 그 결과를 누적하여 합산합니다.
  

---

Code

[ C# ]

using System;
using System.Linq;

class Program {
  static void Main() {
    int len = int.Parse(Console.ReadLine());
    var arrA = Console.ReadLine().Split().Select(int.Parse).ToArray();
    var arrB = Console.ReadLine().Split().Select(int.Parse).ToArray();

    Array.Sort(arrA);
    Array.Sort(arrB);
    Array.Reverse(arrB);

    int sum = 0;
    for (int i = 0; i < len; i++)
      sum += arrA[i] * arrB[i];

    Console.WriteLine(sum);
  }
}

[ C++ ]

#include <bits/stdc++.h>

using namespace std;
typedef vector<int> vi;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int len; cin >> len;

  vi arrA(len), arrB(len);
  for (int i = 0; i < len; i++)
    cin >> arrA[i];
  for (int i = 0; i < len; i++)
    cin >> arrB[i];

  sort(arrA.begin(), arrA.end());
  sort(arrB.rbegin(), arrB.rend());

  int sum = 0;
  for (int i = 0; i < len; i++)
    sum += arrA[i] * arrB[i];
  cout << sum << "\n";

  return 0;
}