[programmers] 최솟값 만들기

최솟값 만들기

 
x
자연수로 이루어진 길이가 같은 수열 A,B가 있습니다. 최솟값 만들기는 A, B에서 각각 한 개의 숫자를 뽑아 두 수를 곱한 값을 누적하여 더합니다. 이러한 과정을 수열의 길이만큼 반복하여 최종적으로 누적된 값이 최소가 되도록 만드는 것이 목표입니다.
​
예를 들어 A = [1, 2] , B = [3, 4] 라면
​
A에서 1, B에서 4를 뽑아 곱하여 더합니다.
A에서 2, B에서 3을 뽑아 곱하여 더합니다.
​
수열의 길이만큼 반복하여 최솟값 10을 얻을 수 있으며, 이 10이 최솟값이 됩니다.
수열 A,B가 주어질 때, 최솟값을 반환해주는 getMinSum 함수를 완성하세요.

 

수학적으로 생각해보자. 어떤 경우에 곱의 합이 가장 작아질까?

우선 가장 작은 수와 가장 큰 수를 곱하고, 그 다음 작은 수와 그 다음 큰 수를 곱하고, 또 그 다음 작은 수와 그 다음 큰 수를 곱해 나가는 식으로 해 전체 합계를 구하면 최솟값을 구할 수 있다.

주어진 예제로 생각해보면 순서대로 곱해서 합하는 경우 1 * 3 + 2 * 4 = 11이 되고, A에서 가장 작은 수와 B에서 가장 큰 수끼리 곱하고 A에서 가장 큰 수와 B에서 가장 작은 수를 곱해 더하면 1 * 4 + 2 * 3 = 10이 되므로 최솟값이 되며, 이 방법이 부합함을 알 수 있다.

두 수열을 각각 정렬해준 뒤, A는 오름차순으로 꺼내고 B는 내림차순으로 꺼내 곱한 값을 총합에 더해준다.

 

 
x
import java.util.Arrays;
​
class TryHelloWorld {
    
    public int getMinSum(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 - i - 1];
            /*System.out.println(answer);*/
        }
​
        return answer;
    }
​
    public static void main(String[] args) {
        TryHelloWorld test = new TryHelloWorld();
        int[] A = { 1, 2 };
        int[] B = { 3, 4 };
        System.out.println(test.getMinSum(A, B));
    }
}