[백준 11501 JAVA] 주식

 

그리디 알고리즘 문제

 

이문제의 접근방법은 앞에서부터 탐색할 것이 아니라, 뒤에서부터 탐색을 하는것이다.

매수점을 찾아 기준을 잡고, 그 앞의 매입점들과의 차이를 구해서 더해주면 된다.

 

마이너스가 될 일은 없다. 뒤에서부터 탐색을해 항상 최대치를 기준으로잡기때문에 조금이라도 높을때엔 사지않는다.

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

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        int N;
        StringTokenizer st;
        int[] arr;
        while (T-- > 0) {
            N = Integer.parseInt(br.readLine());
            st = new StringTokenizer(br.readLine());
            arr = new int[N];
            for (int i = 0; i < N; i++) {
                arr[i] = Integer.parseInt(st.nextToken());
            }
            long answer = 0;
            int max = Integer.MIN_VALUE;
            for (int i = N - 1; i >= 0; i--) {
                if (max < arr[i]) {
                    max = arr[i];
                }
                answer += max - arr[i];
            }
            System.out.println(answer);
        }
    }
}