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

백만 장자 프로젝트

💡 아이디어

처음에 이 문제를 접했을 때 틀을 잡기 위해 10분 정도 고민했다.
일단 이게 어떤 알고리즘에 속할까라는 생각을 했는데 풀고 나니까 그리디가 맞는 것 같다.

가장 간단하게 생각해서 배열에서 최대값을 구하고 그 최대값 앞에 있는 것들은 전부 구매해서 최대값인 날 판매한다고 생각하고

[ sum += 최대값 - 앞에값들 ]

이런식으로 진행해야겠다 생각했다.
중간 중간에 필요한 변수들이 많아서 좀 많이 헷갈렸다..

---

🚨 주의점

처음 이 문제를 풀었다 생각했을 때 테케 10개 중 7개만 맞았고 코드를 생각했을 때 분명 맞을거라 생각했다.

그러나 주의할 점은 범위이다!
테스트 케이스 N이 최대 100만 그리고 매매가 최대는 10000이다.
최악은 1000000일에 첫 일~마지막 전날까지 1이고 마지막 날에 10000인 경우일테고 그렇다면 우리는 int로는 다 담을 수 없다. int는 20억?정도만 저장할 수 있으니까.

최악 : 100만 * 1만 = 100억

---

💻 코드

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


class Solution
{
	public static void main(String args[]) throws Exception
	{
		Scanner sc = new Scanner(System.in);
		int T;
		T=sc.nextInt();
		for(int test_case = 1; test_case <= T; test_case++)
		{
            int saveIdx = 1;
            int day = sc.nextInt();
            long profit = 0;
            int lastSaveIdx =1;
            int[] price = new int[day+1];
            for(int j = 1; j <= day; j++){
             	   price[j] = sc.nextInt();
            }
            
            while(saveIdx < price.length){
             	int curMax = -1;
                int curIndex = 0;
                //최댓값 알아내고
                for(int j = saveIdx; j <= day; j++){
                       if(curMax < price[j]){
                           curMax = price[j];
                           curIndex = j;
                       }
                }

                //최댓값 전까지 구매하고 이득 계산
                for(int i = lastSaveIdx ; i < curIndex; i++){
                       if(price[i] < curMax)
                           profit += curMax - price[i];
                }

                saveIdx = curIndex+1;   
                lastSaveIdx = curIndex + 1;
            }
            System.out.println("#"+ test_case + " " + profit);
		}
	}
}