[Programmers] 최솟값 만들기

최솟값 만들기

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

프로그래머스

풀이

---

import java.util.*;

class Solution
{
    public int solution(int []A, int []B)
    {
        int answer = 0;
        Arrays.sort(A);
        Arrays.sort(B);
        
        for(int i = 0; i < A.length; i++){
            answer += A[i] * B[A.length -1 - i];
        }

        return answer;
    }
}

• 기본적으로 최솟값이 나오기 위해선 “최대의 수”와 “최소의 수”가 항상 곱해져야 한다는 아이디어다.
  • 이는 수학의 재배열 부등식(Rearrangement Inequality)라는 원리로 증명된다.
• 따라서 두 배열을 정렬한다음 한 배열을 역순으로 탐색해주면 된다.