백준 #1026 보물

이번 문제는 문제가 의도하는 뜻만 잘 이해하면 풀 수 있는 문제입니다.  그래서인지 정답자가 상당히 높습니다.  오늘 날짜의 정답자가 8,888명, 정답률 61.5%입니다.  숫자가 8이 연속 4개라서 캡처를 해두었습니다.

 

문제는 두개의 수열 A[*], B[*]이 주어졌을 때, 적절하게 A[*] 수열을 재배치 해서 다음의 식을 최소화하도록 하는 것입니다.

 

\[ \sum_{k} A[k] \cdot B[k] \]

 

문제에서는 B[*] 배열은 재배열하면 안된다고 합니다.  (함정입니다.)

 

문제는 아래 링크에 있습니다.

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

1026번: 보물

B[*] 수열에 가장 a, b 가 있고, a > b라고 해보죠.  A[*] 수열에 c, d 가 있고, c > d 라고 한다면,

ac + bd > ad + bc

인 것은 당연합니다.

 

a > b  -------- 양변에 (c-d) 를 곱합니다.  이 수는 양수이므로 부등호의 방향이 바뀌지 않습니다.

a(c-d) > b(c-d)

ac + bd > ad + bc

 

즉, B[*] 수열에 큰수와 A[*] 수열에 작은수를 서로 곱해주어야지 전체적인 합이 줄어들게 됩니다.

그런데 문제에서는 B[*] 수열을 재배치하지 말라고 합니다.  그러면 A[*] 수열을 어떻게 배치할지 상당히 난감합니다.  그래서 함정이라는 것입니다.  과감하게 B[*] 수열도 재배치하면 됩니다.

 

결국 A[*], B[*] 수열 모두 정렬한 후, A[*] 수열의 작은수들은 B[*] 수열의 큰수와 곱하는 형태로 하면 최소값임을 보장합니다.

 

결국 정렬 문제로 귀결됩니다.

 

아래는 제가 짠 소스입니다.  소스는 참고용으로만 봐주세요.

//----------------------------------------------------------------------------------------
//  baekjoon #1026 - Treasure
//    - by Aubrey Choi
//    - created at 2019-07-06
//----------------------------------------------------------------------------------------
#include <stdio.h>
#include <algorithm>

int main()
{
  int n, a[100], b[100], ans = 0;
  scanf("%d", &n);
  for(int i = 0; i < n; i++) scanf("%d", &a[i]);
  for(int i = 0; i < n; i++) scanf("%d", &b[i]);
  std::sort(a, a + n);
  std::sort(b, b + n);
  for(int i = 0; i < n; i++) ans += a[i]*b[n-i-1];
  printf("%d\n", ans);
}