[백준/파이썬] 1026: 보물

백만년만에 문제 풀이..ㅎㅎ 넘 재밌다.

✅문제 풀이

1026 보물 백준

길이 N인 정수 배열 A와 B가 있다. A 배열을 마음대로 배열할 수 있다.

A 배열과 B 배열의 같은 인덱스에 있는 숫자를 곱한 값을 S라고 하는데, S 의 최솟값을 구하는 문제이다.

조금 생각해 보니, S 최솟값을 구하려면 A 배열에서 큰 값 순서대로 & B 배열에서 작은 값을 순서대로 곱하면 되는 게 떠올랐다. 예제로 테스트해보니 맞는 것 같았따.

B배열은 재배열하면 안된다고 쓰여있는데, 사실 상관 없다. A배열을 재배열해서, 인덱스가 같은 B배열의 숫자를 조정하는 게 포인트니까..!
B배열이 고정되어 있다고 해도, A 배열을 조정해서 원하는 숫자와 매칭시킬 수 있으니까..!!

그래서 A 배열을 오름차순 정렬, B 배열을 내림차순 정렬 후에 같은 인덱스 값끼리 곱해서 더하면 된다!
(A 배열이 내림차순, B 배열이 오름차순이어도 상관 없다.)

 

⚒️ 시간 복잡도

배열 정렬할 때 sort를 사용하는 것 O(NlogN)  &  A, B 배열의 같은 인덱스의 숫자끼리 곱하는 것 O(N) 이니까 => O(NlogN) 이다.

👩‍💻 코드

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)

answer = 0

for i in range(N):
    answer += A[i]*B[i]

print(answer)