문제

문제링크

풀이

데이터를 뒤에서부터 읽으면 쉽다. 먼저 맨 뒤의 숫자를 MAX 값으로 설정한다. 앞 인덱스의 숫자보다 크면 그 차이값을 SUM에 더하고, 작으면 그 앞의 숫자를 MAX로 한다. 이를 데이터 배열 맨 뒤부터 앞까지 수행해주면 된다.

코드

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

public class P1859 {
	public static void main(String[] args) throws Exception, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		// 테스트 케이스 개수
		long t = Integer.parseInt(br.readLine());
		
		for (int i = 0; i < t; i++) {
			// 데이터 개수
			int n = Integer.parseInt(br.readLine());
			
			// 데이터 배열 생성
			int arr[] = new int[n];
			StringTokenizer st = new StringTokenizer(br.readLine());
			for (int j = 0; j < n; j++) {
				arr[j] = Integer.parseInt(st.nextToken());
			}
			
			// 이익 계산
			long gain = 0, max = arr[n - 1];
			for (int k = n - 1; k > 0; k--) {
				if (max > arr[k - 1]) {
					gain += max - arr[k - 1];
				} else {
					max = arr[k - 1];
				}
			}
			
			sb.append("#").append(i + 1).append(" ").append(gain).append("\n");
		}
		System.out.println(sb);
	}
}

입력

3
3
10 7 6
3
3 5 9
5
1 1 3 1 2

출력

#1 0
#2 10
#3 5

결과