[알고리즘 문제 풀이][정렬] 백준 1026번 - 보물 (*)

백준 1026번 보물 문제입니다.

(기초 수학 & 정렬 문제)

 

- 문제 설명: https://www.acmicpc.net/problem/1026

- 문제 풀이:

 

A 배열과 B 배열의 요소를 곱해서 합했을 때 결과가 최솟값이 나오도록 하는 문제입니다.

 

입력

// A 배열
1 1 1 6 0
// B 배열
2 7 8 3 1

출력

18 

// = 1 1 0 1 6
// x 2 7 8 3 1 의 곱의 합

 

결과가 최소값이 되려면 곱셈은 큰 수를 곱하면 너무 커져버리기 때문에 가장 큰 수는 가장 작은 수와 곱해야합니다. 전체 합에서 가장 큰 수는 최대한 적게 포함시키고 가장 작은 수는 최대한 많이 포함시켜야합니다.

 

따라서 A 배열의 가장 큰 수는 B 배열의 가장 작은 수와 매칭되어야하고, A 배열의 가장 작은 수는 B 배열의 가장 큰 수가 매칭되어야합니다. 본 문제를 풀이할 때는 A와 B 를 반대 방향으로 정렬하기만 하면 됩니다. (문제에서 B 배열을 움직이지 않는다는 조건이 있지만, 실제로 정답을 출력할 때 B 배열의 순서는 전혀 상관이 없으므로 정렬해도 상관이 없습니다)

 

- 코드: 

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

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

print(sum([A[i]*B[i] for i in range(N)]))

 

- 실수 포인트 & 반례:

1. B를 정렬하지 않아서 생기는 사소한 실수들 관련

https://www.acmicpc.net/board/view/75907

이 문제의 출제 의도에는 "A만 재배열할 때의 답을 구하는 것이 A와 B를 둘 다 재배열할 때의 답을 구하는 것과 동치임을 알아낼 수 있는가"를 시험하는 것이 포함되어 있습니다.