[백준][1026] 보물

• Problem Link : https://www.acmicpc.net/problem/1026

문제

• 두 정수 배열 A, B가 입력으로 들어온다.
• B의 수의 위치는 고정한 체 A의 수를 재배열하여 S가 최소가 되도록 할 때 S의 값을 구하여라
• $S = A[0] * B[0] + ··· + A[N-1]*B[N-1]$

입력

• 첫째 줄에는 수의 개수 N이 주어진다.
• 둘째 줄에는 A에 있는 N개의 수가 순서대로 주어진다.
• 셋째 줄에는 B에 있는 N개의 수가 순서대로 주어진다.

출력

• 최소가 되는 S의 값을 출력한다.

풀이

S가 최소가 되기 위해서는 큰 값에 작은 값들을 곱하게 만들면 최솟값을 만들 수 있다.

• B의 위치는 고정이므로 A를 재배열하는데 B에서 크기가 큰 순서대로 A의 작은 수들을 곱하게 만들어주면 S값을 최소화 할 수 있다.
• 문제에서는 B의 수의 위치가 고정이라고 했지만 실제 문제에서 물어보는것은 재배열한 A, B가 아니라 S의 값이기 때문에 B의 수의 위치 또한 재배열이 가능하다.
• B의 수의 재배열은 어떻게 보면 A를 재배열한 것이나 다름이 없으므로 문제를 푸는데는 전혀 지장이 없다.
• 큰 수에 작은 수를 곱하기 위해선 B를 큰 순서대로 정렬을 A를 작은 순서대로 정렬하면 된다.

Sort? Sorted?

a = [2, 3, 1]
a.sort()
print(a) #[1, 2, 3]

a = [2, 3, 1]
b = sorted(a)
print(b) #[1, 2, 3]

• sort 함수는 리스트명.sort() 형식으로 “리스트형의 메소드”이며 리스트의 원본값을 직접 수정한다.
• sorted 함수는 sorted(리스트명) 형식으로 “내장 함수”이며 정렬한 리스트를 반환한다.
  • reverse = True를 사용해 내림차순으로 정렬 가능하다.

따라서 리스트 원본을 바로 정렬시키고 싶으면 sort를 원본 값을 유지하고 정렬한 리스트를 새로 얻고 싶으면 sorted를 사용하면 된다.

코드

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)]))