[백준,BOJ 11399] ATM(JAVA 구현)

-풀이

  그리디 알고리즘을 사용하기 적합한 문제의 조건은 1. 각 경우가 독립적인 경우 2. 각 경우의 선택으로 다른 경우에 영향을 미치지 않는 경우를 만족하면 된다고 알고 있다. 이 문제의 경우 각 사람들의 대기시간이 상호 영향을 받지 않는 독릭접인 상태이다. 

 

  그리디 알고리즘을 이용해 손님들의 소요시간을 최소로 만들기 위해서는 먼저 끝나는 사람을 우선으로 처리하면 최솟값이 나오게 된다. 이는 이전의 회의실 배정 문제와 비슷한 유형이라고 생각된다. 그렇기에 문제에서 알려주고 있는 최솟값을 구하는 방법을 코딩으로 옮기기만 하면 된다. 

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

public class Main {

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		
		// 사람의 수 
		int n = in.nextInt();
		
		// 인출하는데 걸리는 시간 배열
		int a[] = new int[n];
		
		for(int i=0;i<n;i++) {
			a[i] = in.nextInt();
		}
		
		// 처리시간이 빠른 사람 순서대로 정렬.
		Arrays.sort(a);
		
		// 가장 빠른 손님의 처리시간으로 초기화.
		int sum = a[0];
		
		// 1번 인덱스부터 이전 손님의 처리시간으로 생기는 대기시간과 자신의 처리시간을 더해 해당 손님이 소요하는 총 시간을 저장한다.
		for(int i=1;i<n;i++) {
			a[i] += a[i-1];
			// 한 손님의 저장된 총 소요시간을 모두 더한다.
			sum+=a[i];
		}
		
		System.out.println(sum);
		in.close();
	}

}