[프로그래머스] 최솟값 만들기 / 파이썬

문제 정리

---

https://programmers.co.kr/learn/courses/30/lessons/12941

길이가 같은 배열 A, B
배열 A, B에서 각각 한 개의 숫자를 뽑아 두 수를 곱합니다.
두 수를 곱한 값을 누적하여 더합니다.
이때 최종적으로 누적된 값이 최소가 되도록 만드는 것이 목표입니다.

배열 A, B가 주어질 때 최종적으로 누적된 최솟값을 반환하는 문제입니다.

제한사항

• 배열 A, B의 크기 : 1,000 이하의 자연수
• 배열 A, B의 원소의 크기 : 1,000 이하의 자연수

입출력 예

A	B	answer
[1, 4, 2]	[5, 4, 4]	29
[1,2]	[3,4]	10

문제 풀이

---

누적된 값이 최솟값이 되려면 더할 값들이 최소가 되야합니다.
더할 값들이 최소가 되기 위해선 각 원소들을 곱한 값이 최소가 되야합니다.
곱할 값이 최소가 되려면 가장 작은 원소와 가장 큰 원소를 곱할 필요가 있습니다.
가장 작은 원소와 가장 큰 원소를 매 곱셈시마다 구하는 것은 비효율적입니다.
배열 하나는 오름차순, 하나는 내림차순으로 정렬하여 순서대로 곱하는 방식을 생각했습니다.

1. A는 오름차순, B는 내림차순으로 정렬합니다.
2. A와 B의 각 원소들을 곱한 값을 answer에 더해줍니다.

def solution(A,B):
    answer = 0
    A = sorted(A)
    B = sorted(B, reverse = True)
    for i in range(len(A)):
        answer += A[i] * B[i]
    return answer