백준 11399 - ATM (자바 - 그리디)

https://www.acmicpc.net/problem/11399

11399번: ATM

 

* 문제 요약

은행에 ATM 이 1대 밖에 없다. 지금 이 ATM 앞에 N 명의 사람들이 줄을 서있다.

사람은 1번부터 N번까지 번호가 매겨져 있으며, i 번 사람이 돈을 인출하는데 걸리는 시간은 Pi 분이다.

 

사람들이 줄을 서는 순서에 따라서 돈을 인출하는데 필요한 시간의 합이 달라진다.

예를 들어 총 5명이 있고, P1 = 3, P2 = 1, P3 = 4, P4 = 3, P5 = 2 인 경우를 생각해보자.

[1,2,3,4,5] 순서로 줄을 선다면, 1번 사람은 3분만에 돈을 뽑을 수 있다. 2번 사람은 1번 사람이 돈을 뽑을 때까지 기다려야 하기 때문에 3+1 = 4분이 걸리게 된다.

3번 사람은 1번, 2번 사람이 돈을 뽑을 때까지 기다려야 하기 때문에 총 3+1+4 = 8분이 필요하게 된다.

4번 사람은 3+1+4+3 = 11분, 5번 사람은 3+1+4+3+2 = 13분이 걸리게 된다.

이 경우에 각 사람이 돈을 인출하는데 필요한 시간의 합은 3+4+8+11+13 = 39분이 된다.

 

줄을 [2,5,1,4,3] 순서로 서면 2번 사람은 1분만에, 5번 사람은 1+2 = 3분, 1번 사람은 1+2+3 = 6분, 4번 사람은 1+2+3+3 = 9분, 3번 사람은 1+2+3+3+4 = 13분이 걸리게 된다.

각 사람이 돈을 인출하는데 필요한 시간의 합은 1+3+6+9+13 = 32분이다.

이 방법보다 더 필요한 시간의 합을 최소로 만들 수는 없다.

 

줄을 서 있는 사람의 수 N 과 각 사람이 돈을 인출하는데 걸리는 시간 Pi 가 주어졌을 때, 각 사람이 돈을 인출하는데 필요한 시간의 합의 최솟값을 구하는 프로그램을 작성하시오.

 

* 입력

첫째 줄에 사람의 수 N (1 <= N <= 1,000) 이 주어진다.

둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi 가 주어진다. (1 <= Pi <= 1,000)

 

* 출력

첫째 줄에 각 사람이 돈을 인출하는데 필요한 시간의 합의 최솟값을 출력한다.

 

* 예시

 

* 해결 과정

그냥 입력받은 값들을 오름차순 정렬한 다음 각 인덱스 별로 자신의 앞쪽에 있는 값들과 자기자신을 합산한 값을 모두 더해주면 되는 문제이다.

 

* 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		int number = Integer.parseInt(br.readLine());
		int[] originArray = new int[number];
		int[] timeArray = new int[number];
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		
		for(int i = 0; i < number; i++) {
			originArray[i] = Integer.parseInt(st.nextToken());
		}
		
		Arrays.sort(originArray);
		
		for(int i = 0; i < number; i++) {
			int sum = 0;
			for(int j = 0; j <= i; j++) {
				sum += originArray[j];
			}
			
			timeArray[i] = sum;
		}
		
		int result = Arrays.stream(timeArray).sum();
		bw.write(result + "\n");
		bw.flush();
		bw.close();
	}
}

 

각자의 돈을 인출하는데 걸리는 시간을 최소화 하기 위해 돈을 인출하는데 시간이 얼마 걸리지 않는 사람이 먼저 돈을 인출하게끔 하는 방식으로 로직을 설계했다.

정렬이 된 이후에는 그냥 목표 인덱스 까지 합산만 해주는 것 자체가 각 단계별로 돈을 인출하는데 걸리는 최소 시간을 찾는데 있어 최적의 경우가 되므로 그리디 알고리즘 문제에 해당된다.