[JAVA / 자바] 백준 11399번_ATM

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

11399번: ATM

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

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

💡 정렬

풀이

- 대기 시간 = 먼저 사용된 인출 시간의 값이 누적되는 방식이므로, 반복되는 부분의 값이 최소여야 하므로 인출 시간이 작은 사람부터 인출 진행

EX) 2, 5, 1, 4, 3(={1, 2, 3, 3, 4}) => 1 + (1 + 2) + (1 + 2 + 3) + ...

    = 1 * 5 + 2 * 4 + 3 * 3 + 3 * 2 + 4 * 1

    = 5 + 8 + 9 + 6 + 4 = 32

 

1. 인출 시간을 오름차순 정렬 후

2. 앞부터 sum += arr[k] * (N-k) 해줌