[SWEA] 1859 백만 장자 프로젝트

1. 배열의 사이즈를 입력받는다.

2. 배열에 값을 넣어준다.

3. 배열에 접근하게 되는데 이때 뒤에서부터 접근한다.

→ 앞에서 접근하게되면 해당 번째의 수가 그 다음에 나올 수보다 크다는 것을 장담할 수 없게 되고, 따라서 그 당시에 파는 가격이 최고 이익을 내는 가격이라고 볼 수 없다.

→ 만약 뒤에서 접근한다면 해당 번째 보다 더 큰 수가 나오기 전까지 샀던 모든 제품을 가장 비싸게 파는 것은 현재 접근한 수라고 보장할 수 있게 된다.(어차피 그 전에 존재하는 큰 수에서는 그 다음에 산 제품을 팔지 못하니까)

4. 만약 가장 큰 수를 갱신할 차례가 오면 현재 발견한 수 다음부터 지금까지 가장 큰 수였던 자리까지 모두 산 가격으로 볼 수 있다. 따라서 그 요소들은 -arr[j]로 계산해주고 MAX 값을 더해준다.

5. 그 다음 MAX값을 현재 발견한 최대 큰 값으로 바꿔준다. 이때 현재 발견한 수 다음은 모두 처리되었으므로

end를 현재 값으로 지정해 준다(배열의 인덱스)

6. 만약 마지막이 가장 큰 수였고 그 전은 점점 작아지는 경우에는 if 문을 거칠 수 없으므로 i가 0일 때를 따로 처리해 준다. 

 

import java.util.Scanner;
import java.io.FileInputStream;
class Solution
{
    public static void main(String args[]) throws Exception
    {
        Scanner sc = new Scanner(System.in);
         
        int T = sc.nextInt();
         
         
        for(int tc = 1; tc <= T; tc++ ) {
            int N = sc.nextInt();
            int[] arr = new int[N];
            int end = N-1;
            long sum = 0;
            for(int i = 0; i < arr.length; i++)
                arr[i] = sc.nextInt();
            long MAX = arr[N-1];
            for(int i = arr.length-1; i >= 0; i-- ) {
                if(arr[i] > MAX) {
                    for(int j = i + 1; j < end; j++) {
                        sum += (-arr[j] + MAX);
                    }
                    MAX = arr[i];
                    end = i;
                }else if(i == 0) {
                    for(int j = 0; j < end; j++) {
                        sum += (-arr[j] + MAX);
                                                 
                    }
                }
            }
            System.out.println("#" + tc + " " + sum);
        }
    }
}