[구현/수학] 백준 1026 보물 - Python

 

[ Contents ]

 

 

1. 문제 (링크 참조)

1026번: 보물

 

 

 

2. 문제 풀이

S = A[0] x B[0] + ... + A[N-1] x B[N-1]

 2개의 배열을 서로 곱해서 최소 합을 구하는 문제입니다. S값을 최소로 만들기 위해 A의 수의 재배열해야 합니다.

 

2022.01.19 - [Algorithm] - [Algorithm] 단골 1번 문제, 구현 / 수학

[Algorithm] 단골 1번 문제, 구현 / 수학

 문제에서는 배열 B는 고정이라고 하지만, 사실 재배열해도 문제가 없습니다. 덧셈은 교환 법칙이 성립하기 때문입니다. 

 S값을 최소로 만들기 위해, 작은 수 * 큰 수의 합으로 만들어 줍니다.

 

 

 

3. 코드

import sys
input = sys.stdin.readline

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

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

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

 

 A배열을 오름차순으로 정렬하고 B배열을 내림차순으로 정렬한 뒤, 두 수를 곱해줍니다.

 sort(reverse=True)는 내림차순으로 정렬합니다.