[Java] 프로그래머스 12941. 최솟값 만들기 (Lv.2)

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

프로그래머스

 

배열 두개의 원소를 하나씩 뽑아 곱해 합을 가장 작게 만드는 문제입니다.

풀이 아이디어부터 말하자면, 두 배열을 정렬해 큰수 - 작은수를 순서대로 짝을 맞춰주면 됩니다. 증명이 떠오르지 않더라도 이렇게 하지 않으면 안된다는 사실은 쉽게 떠올릴 수 있습니다.

 

예를 들어 작은 수 a, 큰 수 A가 있고 작은 수 b, 큰 수 B가 있다고 해봅시다.

a보다 큰 수 A는 두 수의 차이를 n이라고 하면 a + n으로 생각할 수 있습니다. 마찬가지로 B는 b + m으로 생각할 수 있습니다.

작은수 - 큰수 쌍으로 곱한다면, ab + am + ab + bn이 됩니다. 만약 이 순서를 지키지 않고 곱한다면 ab + ab + am + bn + mn이 됩니다. 즉 A와 B가 a와 b보다 큰 mn 만큼 합이 커지게 됩니다. 따라서 작은수가 큰 수와 짝을 이루게 곱해야 더 작은 합이 됩니다.

(제가 수학 전공이 아니기 때문에 수학적 증명은 틀릴 수도 있습니다.)

 

두 배열을 오름차순 / 내림차순으로 정렬을 해 곱해도 되고, 길이가 같기 때문에 둘 다 오름차순으로 정렬해 앞과 뒤에서부터 곱해주어도 됩니다.

 

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[B.length - i - 1];
        }

        return answer;
    }
}