본문 바로가기

코딩 (알고리즘)/그리디

No.11399_ATM

package greedy;
import java.util.*;
public class no11399 {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner scanner = new Scanner(System.in);
		int person = scanner.nextInt(); // N명의 사람
		int[] minute = new int[person]; // i번 사람이 돈을 인출하는 데 걸리는 시간
		for (int i = 0; i<person; i++) {
			minute[i] = scanner.nextInt();
		}
		Arrays.sort(minute); //각 사람의 인출 시간 '최소' 합은, 인출 시간이 작은 사람부터 인출하기
		
		int sum=0; 
//		int sumofsum = 0;
		for (int i=0; i<person; i++) {
				sum += minute[i]*(person-i); 
				//먼저 인출한 사람이 걸린 시간은, 계속 누적된다.
				// 누적되는 횟수만큼 곱해준다.
//			다른 방법 : 각 인출 단계에서 걸린 시간들의 합
//			sum += minute[i];
//			sumofsum += sum;
		}
		System.out.println(sum);	
	}
}

 
각 사람의 인출 시간을 '최소'로 하기 위해서는, 인출 시간이 작은 사람부터 먼저 인출하면 된다.
그러기 위해서는 sort()를 통해, 인출 시간이 작은 순서대로 정렬해 준다.
 
이후 합을 구한다.
먼저 인출한 사람은 뒷사람들이 인출하는 시간에 계속 포함되어 더해진다.
누적되는 횟수만큼 곱해주자.
 
합을 구하는 다른 방법으로는, 
각 인출 단계에서 걸린 시간을 구한 후(sum)
그것들의 합을 구해준다. (sumofsum) 

 메모리 : 20,420KB
걸린 시간 : 264ms


맞힌 사람 중, 본 코드보다 메모리가 반이나 적고 시간도 70ms대로 작은 사람들의 코드를 보니...
로직은 대부분 비슷하나,
BufferedReader, StringTokenizer 등을 사용하였다.
다음번에는 사용해 보자.
 
Array.sort()가 아니라, 직접 quick sort를 구현해 놓은 정답자도 있었다.