백준 1026번 : 보물 (Python)

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

n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
a.sort()
b.sort(reverse=True)
answer = 0
for i in range(n) :
    answer += a[i] * b[i]
print(answer)

배열 $A$와 $B$에 속한 $n$개의 숫자들을 각각 $a_{1} \leq a_{2} \leq \cdots \leq a_{n}$, $b_{1} \leq b_{2} \leq \cdots \leq b_{n}$ 이라고 하자.

이때 문제에서 구하고자 하는 최솟값을 구하기 위해서는 가장 작은 $a_{1}$과 가장 큰 $b_{n}$, 다음으로 작은 $a_{2}$ 와 다음으로 큰 $b_{(n-1)} \cdots$ 이런 식으로 곱해야 한다.

즉 $\sum_{i = 1}^{n}{a_i}{b_{(n+1-i)}}$ 가 되어야 한다.

 

먼저 간단히 증명해보자. $\sum_{i = 1}^{n}{a_i}{b_{(n+1-i)}}$ 에서 중간에 두 쌍을 바꾼다고 가정하자.

$i$$<$$j$, $i+j=n+1$인 임의의 두 수 $i$, $j$에 대해 $a_{i} b_{j}+ a_{j} b_{i}$ 가 $a_{i} b_{i}+ a_{j} b_{j}$ 로 바뀌는 것이다.

이 때 바뀌기 전의 값에서 바뀐 후의 값을 빼보면

$(a_{i} b_{j} + a_{j} b_{i}) - (a_{i} b_{i}+ a_{j} b_{j})$

$= a_{i} b_{j} - a_{i} b_{i} - a_{j} b_{j} + a_{j} b_{i}$

$= a_{i}(b_{j} - b_{i}) - a_j(b_j - b_i)$

$= (a_i - a_j)(b_j - b_i) \leq 0$ 이 되어 바뀌기 전의 값이 더 작거나 같음을 확인할 수 있다.

따라서 처음의 배열 $\sum_{i = 1}^{n}{a_i}{b_{(n+1-i)}}$이 최솟값이다.

 

원하는 순서대로 곱하기 위해서는 A는 오름차순, B는 내림차순으로 정렬한 후

같은 인덱스 번호의 요소끼리 곱하면 된다.