[백준 1026번] 보물

n = int(input())

a = list(map(int,input().split()))
b = list(map(int,input().split()))

a.sort()

a_resort = [0] * n
b_index = []

for i in range(n):
    b_index.append((i,b[i]))

b_index.sort(key=lambda x:-x[1])

for i in range(n):
    a_resort[b_index[i][0]] = a[i] 

sum = 0

for i in range(n):
    sum += (a_resort[i] * b[i])

print(sum)

이번 문제는 전형적인 Greedy 알고리즘 문제로 난이도는 크게 어렵지 않았다.

 

이 문제의 핵심은 배열 A의 원소와 B의 원소간의 곱이 최소가 되도록 하는 것인데, 여기서 우리는 어떤 두 수의 곱이 최소가 되도록 하려면 매 곱마다 '가장 큰 수 * 가장 작은 수'가 되도록 계산을 해야한다는 것이다.

 

따라서 배열 B는 재배열할 수 없기 때문에, 배열 B에서 원소의 값이 가장 큰 순서대로 배열 A의 값이 가장 작은 원소와 곱해주었다.

 

그리디 알고리즘의 핵심인 매 순간마다 가장 좋은 것만 선택하며 푼다는 점을 리마인드 시킬 수 있었던 문제였다 😎