백준 1026 : 보물

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

비교적 간단한 그리디 유형 문제이다.

생각의 흐름

완전탐색을 이용하려면, B의 원소를 배열하는 경우의 수 = 최대 100! 까지 간다.

100 팩토리얼은 진짜 오바기 때문에, 그리디를 생각하게 되었다.

 

간단~하게 생각하면 그냥

$(A의 제일 큰 수 \times B의 제일 작은 수) + (A의 2번째로 큰 수 \times B의 두번째로 작은 수) + ...$

이렇게 나아가면 될 것 같았다.

 

그렇다면 이게 답이라는 것을 어떻게 증명할 것인가?

일단 최적해가 존재한다고 가정하고 생각을 해보았다.

최적해를 수식으로 표현한 뒤에, 만약 그 수식대로 계산되지 않으면 무슨 일이 일어날 지에 대해서 생각해봤다.

증명

A의 원소를 a와 아래첨자로, B의 원소를 b와 아래첨자로 표현한다고 해보자. (eg. $a_{3}, b_{5}$)

최적해 $t$가 존재한다고 했을 때, 이 $t$가 계산되는 식이 아래와 같다고 해보자.

$t = a_{1}b_{1} + a_{2}b_{2} + ... + a_{n}b_{n}$

 

우리의 가정은 a는 뒤로 갈수록 작아진다는 거고, b는 뒤로 갈수록 커진다는 것이다.

$a_{1} > a_{2} > ... > a_{n}$

$b_{1} < b_{2} < ... < b_{n}$ 

 

이때 $a_{1}b_{1}$에서, $b_{1}$이 아니라 다른 B의 원소를 곱한다고 생각해보자.

그 임의의 원소를 $b_{k}$라고 하겠다.

 

그렇다면 원래 $b_{k}$가 곱해져야 했던 $a_{k}$에는 $b_{1}$이 곱해진다.

그러면 기존의 $a_{1}b_{1} + a_{k}b_{k}$에서, $a_{1}b_{k}+a_{k}b_{1}$이 계산되는 것이다.

 

$(새로운 계산식) - (기존의 계산식)$은

$a_{1}b_{k}-a_{1}b_{1}+a_{k}b_{1}-a_{k}b_{k}$이고,

이 식을 정리하면 $a_{1}(b_{k}-b_{1})-a_{k}(b{k}-b_{1}) = (b_{k}-b_{1})(a_{1}-a_{k})$가 된다.

 

여기서 우리의 가정에 따르면 $a_{1} > a_{k}, b_{1} < b_{k}$이므로,

$(b_{k}-b_{1})(a_{1}-a_{k}) > 0$이 된다.

$(새로운 계산식) - (기존의 계산식) > 0$이라는 말은, 새로운 계산식이 더 크다는 이야기이다.

 

결론적으로, 새로운 계산식이 기존의 계산식보다 더 크다는 것은

A의 원소 중 가장 큰 값인 $a_{1}$이 $b_{1}$과 곱해지지 않으면, 총합이 더 커진다는 뜻이다.

 

즉, A의 가장 큰 원소 $a_{1}$에는 $b_{1}$이 곱해져야 합이 가장 작아진다.

 

$a_{2}$에 대해서는, $a_{1}$과 $b_{1}$을 제외한 나머지 원소들에 대해서 위와 같은 내용이 성립한다.

$a_{n}$까지에 대해서도 같은 설명이 가능하다.

따라서 최적해는, 우리의 가정을 따르는 해와 같다고 말할 수 있다.

코드

N = int(input())

A = list(map(int, input().split()))
B = list(map(int, input().split()))

A.sort(reverse=True)
B.sort()

total = 0
for i in range(N):
  total += A[i] * B[i]

print(total)