SW Expert Academy 1859 백만장자 프로젝트

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        StringBuilder sb = new StringBuilder();

        int T = sc.nextInt();
        int idx = 0;

        while (idx < T) {
            int N = sc.nextInt();

            int[] arr = new int[N];
            for (int i = 0; i < N; i++) arr[i] = sc.nextInt();

            long sum = 0;
            int max_value = 0;
            for (int i = N - 1; i >= 0; i--) {
                if (arr[i] > max_value) max_value = arr[i];
                else sum += max_value - arr[i];
            }

            sb.append("#").append(++idx).append(" ").append(sum).append("\n");
        }

        System.out.println(sb);
    }

d2 난이도인데 생각외로 시간이 걸렸다.
이 문제는 뒤에서부터 순회해야 더 쉽게 해결할 수 있다.
인풋이 최대 백만개이고 가격이 1만이하로 제공되므로 (1백만 * 1만 > 21억)
int 범위를 초과하므로 long을 사용해야한다