[BOJ/PYTHON] 1026. 보물

백준 문제 링크: https://www.acmicpc.net/problem/1026

문제 요약

길이가 N인 정수 배열 A와 B

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

S의 값을 최소로 만들기 위해 A의 수를 재배열 (A만)

S의 최솟값을 출력

핵심 아이디어

A를 재배열해 B의 가장 큰 수와 A의 가장 작은 수가 곱해지게 하면 된다!

B는 재배열하면 안 된다고 문제에 써져 있는데, 재배열된 후의 A 배열을 문제에서 요구하고 있지 않으니 그냥 B 배열도 원하는 대로 섞어도 된다.

따라서 B는 큰 수부터 정렬, A는 작은 수부터 정렬하고, 곱한 값을 차례대로 더하면 된다.

풀이

# silver4-1026. 보물

import sys
input = sys.stdin.readline

n = int(input()) # 길이
a = list(map(int, input().split())) # A 배열
b = list(map(int, input().split())) # B 배열

# A를 재배열해 B의 가장 큰 수와 A의 가장 작은 수가 곱해지게 해야 함
# A 오름차순, B 내림차순 정렬하면 됨. 근데 B는 정렬하면 안 되는데 어떡하지..?
# 둘 다 정렬해서 계산해도 A는 원본 배열 바꾸고 B는 얕은 복사로 하면 되지 않을까
# 문제에서 재배열된 A배열을 요구하지 않으니까 신경 안 쓰고 저렇게 해도 될 듯

a.sort()
b.sort(reverse=True)

sum = 0
for i in range(n):
  sum += a[i] * b[i]
print(sum)

실행 시간

메모리 30864KB, 시간 72ms (python3)