[JAVA] BOJ 11399 ATM

 출처 : 백준

 

그리디 알고리즘 문제 중에서도 가장 쉬운 문제인 것 같다.

각 사람이 돈을 인출하는데 필요한 시간의 합의 최솟값을 찾는 문제인데 단순하게 각 사람의 기다리는 시간이 주어졌을 때 오름차순으로 정렬해서 세우는 것이 최소이다. 왜냐하면 돈을 인출하는데 걸리는 시간이 긴 사람이 앞에 있으면 계속 누적이 되기 때문에 값이 커질 수밖에 없다. 따라서 주어진 배열을 오름차순으로 정렬한 다음 각 요소를 이전 값까지의 누적 값과 더해 새롭게 저장한다. 즉, A(i) = A(i-1) + A(i) 이다. 

 

Input에는 BufferedReader 와 Output에는 System.out.println을 사용했다.

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int[] arr = new int[N];
		st = new StringTokenizer(br.readLine());
		for(int i=0; i<N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		Arrays.sort(arr);
		for(int i=1;i<N;i++) {
			arr[i]+= arr[i-1];
		}
		int sum=0;
		for(int i: arr) {
			sum+= i;
		}
		System.out.println(sum);
	}

}

arr배열에 각 사람들이 기다리는 시간의 값을 넣어준 다음 오름차순으로 정렬, 그 후엔 각 요소의 값을 이전의 값과 더해준 값으로 재정의를 해준다. arr [i] += arr [i-1] 

마지막은 각 요소를 다 더해준 값을 출력해주면 된다.