[Algorithm] 1859. 백만 장자 프로젝트 (SWEA)

출처

1859. 백만 장자 프로젝트

[입력]

첫 번째 줄에 테스트 케이스의 수 T가 주어진다.

각 테스트 케이스 별로 첫 줄에는 자연수 N(2 ≤ N ≤ 1,000,000)이 주어지고,

둘째 줄에는 각 날의 매매가를 나타내는 N개의 자연수들이 공백으로 구분되어 순서대로 주어진다.

각 날의 매매가는 10,000이하이다.

---

일단 나는.. 문제 이해는 했지만 접근하는 방법이 다 틀렸었다. 그래서 유튜브와 다른 자료를 찾아서 문제 해결을 했다....

접근 1)

이 입력에서 부터 자료형 타입을 유추를 해야 했는데, 나는 그러지 못했다ㅠㅠ...

매매가는 각 날마다 최대 10,000 이하이고, 최대 1,000,000일 동안 주어진다. 그리고 하루의 최대가격은 10,000원 이다. 여기서 최악의 수인 10,000원 * 1,000,000 일 = 100억 을 생각을 해야했다. 그 이유는 Java에서 int타입의 최대는 약 21억이기 때문이다 그래서 long타입으로 문제를 풀어야 한다는 것을 유추를 해야만 이 문제를 해결 할 수 있었다.

접근 2)

함수를 뒤에서부터 배열을 순회하며 최대 이익을 계산하는 방식으로 접근을 해야 했다.

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[] prices = new int[N];
            
            for(int i = 0; i < N; i++){
            	prices[i] = sc.nextInt();
            }
            
            long profit = maxProfit(prices);
            
            System.out.println("#" + tc + " " + profit);
            
        }
	}
    
    private static long maxProfit(int[] prices){
    	long profit = 0;
        
        int max = 0;
        
        for(int i = prices.length-1; i >=0; i--){
        	int today = prices[i];
            if(max > today){
            	profit += max - today;
            }else{
            	max = today;
            }
        }
        
        return profit;
    }
}