[Python] 백준 1026번. 보물 (실버2)

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

1026번: 보물

 

예전에 풀었던 문제들을 복습하면서 정리중입니다.

 

아이디어를 떠올리기 어렵지만 구현은 간단한 문제입니다.

A에 있는 수와 B에 있는 N개의 수를 하나씩 뽑아 곱해 더하고 그 누적합을 최소로 만드는 문제입니다.

 

해결방법은 간단합니다.

A에서 가장 작은수를 B에서 가장 큰수, 그 다음으로 작은 수를 다음으로 큰 수와 곱하는 식으로 계산해주면 됩니다.

문제의 조건에선 B를 재배열하지 말라고 하지만... 요구하는 정답이 A의 배열이었다면 몰라도 누적합이기 때문에 그냥 신경쓰지 않고 정렬해줘도 상관없습니다.

생각

예를 들어 2,8,1과 6,3,5가 입력으로 주어졌다고 가정해봅시다.
이를 각각 오름차순 내림차순으로 정렬하면 1,2,8과 6,5,3이 됩니다. 
문제의 정답은 앞에서부터 순서대로 두 집합의 수를 곱한 6 + 10 + 24 = 40이 됩니다.
6,3,5의 배열이 바뀌었지만 1,2,8과 6,5,3의 곱의 위치를 바꾸어 1,8,2와 6,3,5로 생각해도 답은 같습니다. 
그냥 적합한 순위의 수를 매번 찾기가 귀찮아 정렬해 놓았다고 생각해 버립시다.

 

 

아이디어가 맞는지 생각해 보겠습니다.

A에서 기존의 가장 작은 수를 a 라고 하면 a가 아닌 어떤 수는 a+c로 나타낼 수 있을겁니다. (a와 같을 수 있음, 즉 c≥0)

B에서 가장 큰 수를 b라고 하면 b가 아닌 어떤 수는 b-d로 나타낼 수 있을겁니다. (마찬가지로 d≥0)

아이디어가 틀리다면 다른 순서로 수를 배열했을때 합이 더 작아져야합니다.

 

다른 순서로 수를 배열한다면 기존의 (a * b) + ((a+c) * (b-d))가 (a * (b-d)) + ((a+c) * b)로 대체될겁니다.

 

각 식을 계산해 풀어주면 1. ab + ab + cb - ad - cd 와 2. ab - ad + ab + cb가 됩니다.

다른 수를 선택해서 합이 더 작아지는 케이스가 있다면 1번 식보다 2번 식이 더 작아야합니다.

즉 1번식 - 2번식 > 0 이 성립해야하는데, 계산해보면 cd < 0이 되고 c와 d는 각각 0 이상의 정수이기 때문에 성립하지 않습니다. (c와 d가 둘 다 0이라면 같은 크기일 순 있지만, 이때의 선택도 정답 조합의 하나가 됩니다.)

 

따라서 A에서 가장 작은 a와 B에서 가장 큰 b를 곱하는게 최소값이 되는 조합이고, 이렇게 fix된 a와 b를 제외한 A' B'로 다시 최소합을 구한다고 생각하면 같은 증명으로 A와 B의 크기가 1이 될 때까지 적용이 가능합니다. 

둘의 크기가 1이라면 당연히 곱할 수 있는 방법이 하나밖에 없겠죠.

 

따라서 위와같이 정렬된 A와 역정렬된 B를 순서대로 곱한 합이 최소값입니다.

 

(제가 수학전공이 아니기 때문에 증명은 틀릴 수 있습니다... )

 

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(0,n):
    answer += int(A[i]) * int(B[i])

print(answer)