[Java]그리디 알고리즘 - 배열에서 2개씩 짝지을때 합의 최댓값이 최소가 되게할려면

1. 문제

 

"""

2 * N개의 숫자가 주어졌을 때, 겹치지 않으면서 2개의 원소가 하나의 그룹을 이루도록 하여 총 N개의 그룹을 만드려고 합니다. 적절하게 그룹을 만들어 각 그룹에 있는 원소의 합 중 최댓값이 최소가 되도록 하는 프로그램을 작성해보세요.

 

예를 들어 N = 2, 주어진 원소가 3, 5, 5, 2 였을 때

그룹을 [5, 5], [3, 2]로 나눈다면 각 그룹에 있는 원소의 합은 순서대로 10, 5 이므로 이 중 최댓값은 10이 됩니다.

만약 그룹을 [3, 5], [5, 2]로 나눈다면 각 그룹에 있는 원소의 합은 순서대로 8, 7 이 되므로 이 중 최댓값은 8이 되며 이보다 최댓값을 더 작게 만들 수는 없습니다.

 

"""

 

2. 풀이

 

항상 문제부터 똑바로 이해해야돼

 

2N개의 숫자를 N개 N개씩 2개 그룹으로 나누는게 아니라... 2개씩 짝지어서, N개 그룹을 만들려는게 핵심이고

 

어떻게 2개씩 짝지어야, N개 그룹들에서 합의 최댓값이 최소가 될 수 있을까

 

그거는 매 순간, 최댓값과 최솟값을 짝지어야 전체 N개 그룹에서 합의 최댓값이 최소가 될 수 있다.

 

왜냐하면,

 

N개의 수를 오름차순으로 정렬해서 $a_{1}, a_{2}, ... , a_{N}$으로 만들었다고 했을 때,

 

$a_{N}$은 어떠한 수 보다도 더 크다.

 

남은 하나와 짝을 지었을때, 어떠한 수와 짝을 지어야 합이 가장 작아질 수 있을까?

 

당연히 $a_{1}$이다. 

 

마찬가지로 $a_{2}, ..., a_{N-1}$에서 $a_{N-1}$은 현재 어떠한 수보다도 더 크다.

 

그렇다면 어떠한 수와 짝을 지어야 합이 가장 작아지는가?

 

당연히 $a_{2}$이다.

 

따라서 매 순간 배열에 남은 수에서 최댓값과 최솟값을 묶어야, 두 수의 합이 가장 작아질 수 있다.

 

그리고 이렇게 묶어야 전체 N개의 그룹을 만들었을 때, 이들 각각 그룹의 합의 최댓값은 모든 경우에서 가장 작아진다.

 

실제로 

 

[a2,aN], [a1,aN-1] 을 생각해보자.

 

여기서 합의 최대는 a2+aN이다.

 

이번엔, a1과 a2를 바꿔서 [a1,aN], [a2,aN-1] 으로 해보면, a1+aN과 a2+aN-1 모두 합의 최대가 될 수 있지만

 

이들은 a2+aN보다 작다.

 

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        // 여기에 코드를 작성해주세요.

        Scanner sc = new Scanner(System.in);

        int n = 2*sc.nextInt();
        int[] arr = new int[n];

        for(int i = 0; i < n; i++){
            arr[i] = sc.nextInt();
        }

        Arrays.sort(arr);

        int max = 0;

        for(int i =0; i<n; i++){
            int sum = arr[i] + arr[n-1-i];

            if(max < sum){
                max = sum;
            }
        }

        System.out.println(max);

    }
}

 

명확히 일반적인 경우에서 증명이 안된 느낌인데

 

직관은 맞는데