SW Expert 1859. 백만장자프로젝트 (Java)

최대이익찾기

 

입력 : 3 5 9

출력 : 10

 

입력 : 1 1 3 1 2

출력 : 5

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;
        T = sc.nextInt();
       
        long results[] = new long[T];
 
        for (int test_case = 1; test_case <= T; test_case++) {
            int n = sc.nextInt();
 
            int arr[] = new int[n];
 
            long result = 0;
            for (int i = 0; i < n; i++) {
                arr[i] = sc.nextInt();
            }
 
            int maxValue = 0;
            for (int i = n - 1; i > -1; i--) {
                maxValue = Math.max(arr[i], maxValue);
                result += (maxValue - arr[i]);
            }
 
            results[test_case - 1] = result;
        }
 
        for (int i = 0; i < T; i++) {
 
            System.out.println("#" + (i + 1) + " " + results[i]);
        }
 
    }
}

 

 

뒤에서부터 계산하면서 max값을 뺀 숫자를 더한다.

뒤에서부터 계산하는 이유는 사고 난 뒤에 팔기 때문에 금액이 클때 파는 것이 유리하므로 max값일 때 판매

 

3 5 9일때는 9 5 3순으로 돌아가면서

9는 max이므로 9-9 = 0

5는 max인 9 - 5 = 4 이익

3은 max인 9 - 3 = 6 이익

결과는 4 + 6인 10 이익

 

다만 memory초과 에러가 발생했는데 int범위가 초과해서 발생하는 문제

results를 long으로 선언해야 통과함