🔑 핵심 원리 (재배열 부등식, Rearrangement Inequality)
- 두 배열을 같은 순서(오름차순-오름차순)로 곱하면 합이 최대가 됩니다.
- 두 배열을 반대 순서(오름차순-내림차순)로 곱하면 합이 최소가 됩니다
즉:
- 최소값:
A를 오름차순 정렬,B를 내림차순 정렬 → 곱한 합 - 최대값:
A,B둘 다 오름차순 정렬 → 곱한 합
A = [1, 4, 2]
B = [5, 4, 4]
(1*4) + (2*4) + (4*5) = 4 + 8 + 20 = 32 (최대)
(1*5) + (2*4) + (4*4) = 5 + 8 + 16 = 29 (최소)