[BOJ 1026] 보물

1) 문제 링크

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

2) 접근

1402번과 마찬가지로 특수한 경우부터 고려해봤다.
A가 0을 포함하는 경우? -> B의 가장 큰 수부터 곱해야지…
B가 0을 포함하는 경우? -> A의 가장 큰 수부터 곱해야지…

일단 이렇게 생각하고 0을 포함하지 않는 경우에 대해 고려하기 시작했는데, 문득 A를 내림차순으로, B를 오름차순으로 정렬한 뒤 곱해버리면 될 것 같다는 생각이 들었다. 더군다나 문제에서 B를 재배열하지 않는다고 했지만, 재배열 하나마나 결과는 똑같기도 했기 때문이다.

일단 {A[0], …, A[n-1]}, {B[0], …, B[n-1]}을 오름차순으로 정렬한 수열을 각각 ${a_1, a_2, …, a_n}$, ${b_1, b_2, …, b_n}$이라 하자.

• $n = 1$: 최솟값은 $a_1b_1$임이 자명하다.
• $n = 2$: $a_1b_1+a_2b_2$가 크냐, $a_2b_1+a_1b_2$가 크냐의 문제다. 대소비교할 때 쓰는 여러 방법 중 두 수를 빼서 부호 판별하는 방법이 있고, 다른 방법들 보다 쓰기 편해 보이니 이를 선택했다.
  $(a_1b_1+a_2b_2)-(a_2b_1+a_1b_2) = (a_1-a_2)(b_1-b_2) \geq 0$. 따라서 $a_1b_1+a_2b_2 \geq a_2b_1+a_1b_2$가 성립한다. 즉, $a_1$, $a_2$, $b_1$, $b_2$의 값에 관계없이 $a_1 \leq a_2$, $b_1 \leq b_2$이면 위 명제가 성립한다는 것이다. 따라서 최솟값은 $a_2b_1+a_1b_2$임이 증명됐다.
• $n = 3$: 뭐.. 직관적으로는 $a_3b_1+a_2b_2+a_1b_3$일 텐데. 일단 이러한 곱을 기준으로 삼자.
  ① 기준인 형태와 두 항만 다른 경우: 동일한 한 개의 항은 빼두고, 나머지 두 항만 $n = 2$일 때의 증명을 이용하면 $a_3b_1+a_2b_2+a_1b_3$보다 작을 수 없음이 증명된다.
  ② 기준인 형태와 세 항 모두 다른 경우: 두 항을 잡아서 $n = 2$일 때의 증명을 이용해 ①의 형태로 만들면 ①과 마찬가지로 $a_3b_1+a_2b_2+a_1b_3$보다 작을 수 없음이 증명된다.
• $n \geq 4$: $n = 3$일 때의 아이디어를 생각해보면 결국 어떤 형태든 간에 두 항을 잡고 $n = 2$일 때의 증명을 이용하는 것을 반복하다 보면 $a_nb_1+…+a_1b_n$보다는 작을 수 없음이 증명된다.

따라서 모든 자연수에 대해 직관이 맞음을 증명했고, 이를 바탕으로 문제를 풀었다.

3) 풀이

#include <iostream>
#include <algorithm>
using namespace std;

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

    int n, sum=0;

    cin >> n;
    int a[n], b[n];
    for(int i=0; i<n; ++i){ cin >> a[i]; }
    for(int i=0; i<n; ++i){ cin >> b[i]; }

    sort(a, a+n); sort(b, b+n);

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

    return 0;
}

4) 피드백

딱히? 다만… 내 생각엔 충분히 구성적인 문제인데 딱히 구성적이라는 언급이 없는 걸 보면 내 발상이 너무 불필요하게 복잡한 것일수도 있다.