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

https://swexpertacademy.com/main/code/problem/problemDetail.do

SW Expert Academy

문제 풀이

푸는 방법만 알면 진짜 간단하게 작성한다. 본인은 이상한 곳에서 시간을 허비해서 꽤 오래 걸렸지만 이걸 보는 사람들은 시간낭비 하지 말길 바란다..
우선 언제 사서 언제 팔지 모른다. 계속 체크해가며 가장 비싼 비용에 되팔아야 한다는 말이고 발생할 수 있는 모든 경우를 예측하기 위해 정보들을 기억해야 한다.
이것만 기억하자

예측 -> 뒤에서 부터 탐색

대부분 예측해야 하는 문제는 뒤에서부터 탐색하면 잘 풀린다.
물론 앞에서부터 할 수도 있을 것이다. 하지만 저장해야 할 정보도 많고 매우 복잡해진다.

다음 소개할 코드는 뒤에서부터 탐색을 한 코드인데 앞에서부터 탐색을 해봐도 좋다. 정말 힘들다,,,

코드

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

public class Solution {

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int T = Integer.parseInt(br.readLine());

        for(int tc=1; tc<=T; tc++) {
            int n = Integer.parseInt(br.readLine());
            int[] a = Arrays.stream(br.readLine().split(" "))
                    .mapToInt(Integer::parseInt)
                    .toArray();

            int max = a[n-1];
            long ans = 0;

            for(int i=n-2; i>=0; i--) {
                if(max>a[i]) 
                    ans += max-a[i];
                else 
                    max = a[i];
            }
            sb.append("#"+tc+" "+ans+"\n");
        }
        System.out.print(sb);
    }
}