[JAVA]백준 11399 ATM

JAVA로 풀이했습니다.
출처 : 백준 알고리즘 https://www.acmicpc.net

문제 개요

11399번 문제 👉 https://www.acmicpc.net/problem/11399
배열을 조합하여 각자의 시간을 최소로 하는 경우 찾기
난이도 👉 실버 3

풀이과정

배열을 조합하여 각자의 시간을 최소로 하려면 배열을 정렬시켜서 가장 걸리는 시간이 작은 사람부터 업무를 보게하면 된다.

나만의 방법

처음에 순열로 모든 경우의 수를 탐색하여 순서에 따른 값을 계산하려고 설계하였다. 결과는 시간복잡도 초과 그래서 다시 N의 범위를 확인하니 1000이었다. 나의 계산은 1000!만큼의 시간복잡도를 사용하였기 때문에 시간초과가 날수 밖에 없었다. 따라서 그리디라는 것을 인지하였고, 수학적으로 각자의 시간이 최소가 되는 경우를 생각해보니 정렬된 경우라는 것을 생각하여 문제를 해결할 수 있었다.

소스코드

public class baek_11399 {
	static int N, arr[];

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

}