[BAEKJOON] - 11501번 : 주식

11501번 문제 링크

📜 알고리즘 접근 방법

위 문제를 접근하는 방법은 "역방향 탐색법"을 사용하는 것입니다.

역방향 탐색이란 별개 아니라 말그대로 배열을 역순으로 탐색한다는 것을 의미합니다.

주식으로 최대의 이익을 보기 위해서는 판매 가격과 구매 가격 간의 격차가 커야 합니다. 역방향 탐색으로 진행해야 판매금액이 가장 커집니다.

예시로 나와있는 TestCase를 보면, 1 1 3 1 2 라는 수열이 있습니다.

이를 역방향 탐색을 적용해보면, 다음과 같습니다.

2 = max > 0 // max 값은 0으로 초기화된 상태라고 가정합니다.

2 = max > 1, // max 값을 비교하여 보다 크면 max값으로 초기화, 아닌 경우 뺀 값을 결과값에 추가.
2 - 1 = 1, result = result + 1

3 = max > 2

max > 1,
3 -1  = 2, result = result + 2

max > 1,
3 -1  = 2, result = result + 2

👾 성공

import java.io.*;
import java.util.*;

public 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[] now;
        
        StringBuilder sb = new StringBuilder();
        
        while(t-- > 0){
            int n = Integer.parseInt(br.readLine());
            
            now = new int[n];
            
            StringTokenizer st = new StringTokenizer(br.readLine());
            
            for(int i=0; i < n; i++){
                now[i] = Integer.parseInt(st.nextToken());
            }
            
            long sum = 0;
            
            long max = 0;
            
            for(int i = now.length -1; i >= 0; i--){
                if(now[i] > max){
                    max = now[i];
                }else{
                    sum += (max - now[i]);
                }
            }
            
            sb.append(sum).append("\n");
        }
        
        br.close();
        
        System.out.println(sb);
    }
}