[수학] 곱의 합의 최솟값

1. 핵심 전략

한 배열은 오름차순, 다른 배열은 내림차순 정렬 후 같은 인덱스끼리 곱합니다.

Arrays.sort(A);              // 오름차순
Arrays.sort(B);              
// B를 내림차순으로 (역순)
for (int i = 0; i < n; i++) {
    answer += A[i] * B[n-1-i];
}

Why?

• 큰 숫자 × 큰 숫자 = 결과가 폭발적으로 증가
• 큰 숫자 × 작은 숫자 = 큰 숫자의 영향력 최소화
• 예: [1, 4, 2] × [5, 4, 4]
  • 같은 순서: 1×5 + 4×4 + 2×4 = 29
  • 역순 정렬: 1×5 + 2×4 + 4×4 = 29 ❌
  • 올바른 역순: 4×4 + 2×4 + 1×5 = 29 ❌

A: [1, 2, 4] (오름차순)
B: [5, 4, 4] (내림차순)
   1×5 + 2×4 + 4×4 = 29

반대로:
A: [1, 2, 4]
B: [4, 4, 5]
   1×4 + 2×4 + 4×5 = 32 (더 큼!)

2. 수학적 근거

재배열 부등식 (Rearrangement Inequality)

• 최솟값: 한 수열 오름차순 × 다른 수열 내림차순
• 최댓값: 둘 다 같은 순서 정렬

3. 패턴 정리

목표	정렬 방법
곱의 합 최소화	역순 정렬 (A↑ × B↓)
곱의 합 최대화	같은 순서 (A↑ × B↑)

4. 관련 문제

• 프로그래머스 - 최솟값 만들기
• 그리디 알고리즘 기초 문제
• "역순 정렬로 최소화" 패턴 기억! ⭐

5. 구현 코드

class Solution {
    public int solution(int[] A, int[] B) {
        Arrays.sort(A);  // 오름차순
        Arrays.sort(B);  // 오름차순
        
        int answer = 0;
        for (int i = 0; i < A.length; i++) {
            answer += A[i] * B[B.length - 1 - i];  // B는 역순으로
        }
        return answer;
    }
}