Greedy 접근법 - 백준 20044번

위의 문제에 대해 설정한 알고리즘은 다음과 같다. 

1) 우선 학생들의 코딩역량을 오름차순으로 정리한다. 

2) 최소값을 최대가 되게 만들어야하므로 1+n, 2+n-1, 3+n-2, 4+n-3... 의 식으로 더해주는 것이 최적의 방법이다. (like 가우스 계산법) 

3) 최솟값을 계속해서 업데이트 해주고, 마지막에 최솟값을 출력해준다. 

 

실제 코드는 다음과 같다. 

 

import java.util.Arrays;
import java.util.Scanner;
 
public class project_group {
 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int team_number, min_value, result;
        Scanner scanner = new Scanner(System.in); 
        team_number=scanner.nextInt(); //몇개의 팀으로 구성될지 사용자로부터 입력받는다. 
        
        int score[] = new int[2*team_number]; //각 팀은 2명으로 구성되어 있기때문에, 다음과 같이 score함수를 선언해준다. 
        
        for(int i = 0; i<score.length; i++) { // 각 학생의 점수(코딩역량)을 입력받는다. 
            score[i] = scanner.nextInt();
        }
        
        Arrays.sort(score); // 입력받은 점수들을 오름차순으로 정렬해준다. 
        
        min_value = 300000; // 절대 나올 수 없는 값으로 min값을 설정해준다. 
        
        for(int j = 0; j<team_number; j++) {
            
            result = score[j]+score[team_number*2-(j+1)]; //최솟값을 최대가 되게 해주어야하기때문에, 정렬된 점수들을 다음과 같이 2개씩 더해준다.(가우스 덧셈을 연상해보면 쉽게 이해 가능)
            if(min_value>result) min_value=result; // 최솟값을 출력해줘야하기 때문에, 더한 값이 현재의 최솟값보다 작다면 최솟값을 update해준다. 
        }
        
        System.out.println(min_value); // 최솟값을 출력해준다. 
        
        
    }
 
}