[Algorithm] 백준 1026

문제

옛날 옛적에 수학이 항상 큰 골칫거리였던 나라가 있었다. 이 나라의 국왕 김지민은 다음과 같은 문제를 내고 큰 상금을 걸었다.

길이가 N인 정수 배열 A와 B가 있다. 다음과 같이 함수 S를 정의하자.

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

S의 값을 가장 작게 만들기 위해 A의 수를 재배열하자. 단, B에 있는 수는 재배열하면 안 된다.

S의 최솟값을 출력하는 프로그램을 작성하시오.

풀이

내가 생각한 알고리즘

문제에서는 A를 재배열하고 B를 재배열하지 말라고 명시되어 있지만, 이 문제에서 구해야하는 것은 S의 최솟값이다.

그래서 A를 정렬하고, B를 반대로 정렬한 것의 총합을 구해서 답을 구하였다.

코드

N = int(input())

A = list(map(int, input().split(' ')))
B = list(map(int, input().split(' ')))

S = 0

A.sort()
B.sort(reverse=True)

for i in range(0, N):
    S += A[i]*B[i]

print(S)