[알고리즘] 백준 1026번 보물

문제

https://www.acmicpc.net/problem/1026

1026번: 보물

 

문제 접근

가장 작은 값을 만들기 위해서는 (a 배열에서 가장 큰 값 * b 배열에서 가장 작은 값) 에서 (a 배열에서 가장 작은 값 * b 배열에서 가장 큰 값) 의 형태로 더해줘야지 최솟값이 나오게 된다. 즉, 그리디를 사용하자!

 

코드

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(0,n):
    sum += a[i]*b[i]

print(sum)

 

배운점

쉬운 그리디 문제는 보통 리스트와 그에 대한 정렬을 이용해서 많이 풀 수 있다는 것을 느낄 수 있었다.