[백준] 11399번 : ATM 자바(Java)

문제

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

입력

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

출력

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

접근방식 및 풀이

돈을 인출하는데 필요한 시간이 작은 사람 순으로 정렬을 해야 최솟값을 구할 수 있다. 따라서 돈을 인출하는데 걸리는 시간을 오름차순으로 정렬한 후, 누적된 값을 더한다. 즉, 예제에 있던 [3 ,1 ,4 ,3 ,2] 배열을 [1 ,2 ,3 ,3, 4]로 오름차순 정렬하고 아래과 같이 계산한다.

1 = 1
1+2 =3
1+2+3 =6
1+2+3+3 =9
1+2+3+3+4 =13

각 사람이 필요한 최솟값을 더하면 1+3+6+9+13=32가 나온다.

코드

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

public class Main {
	
	
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt();
		int cnt = 0;
		int arr[] = new int[n];
		
		for(int i=0; i<n; i++) {
			arr[i]= sc.nextInt();
		}
		
		Arrays.sort(arr);
		
		
		for(int i = 0; i<arr.length; i++) {
			for(int j =0; j<=i; j++) {
				cnt = cnt + arr[j];
			}				
			
		}
		System.out.println(cnt);
		
		
		
	}
	

	
}

처음에는 위의 코드로 풀었다. 정답이 나왔지만 이중for문을 쓰는건 너무 비효율적인 것 같아서 아래의 코드로 변경했다.

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

public class Main {
	
	
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt();
		
		int arr[] = new int[n];
		
		for(int i=0; i<n; i++) {
			arr[i]= sc.nextInt();
		}
		
		Arrays.sort(arr);
		
		int cnt = 0; // 각 사람이 돈을 인출하는데 걸린 시간
		int sum = 0;// 누적된 시간
		
		for(int i = 0; i<arr.length; i++) {
			
			sum += cnt + arr[i];
			cnt += arr[i];
			
		}
		System.out.println(sum);
		
		
		
	}
	

	
}