[Java] 1859. 백만 장자 프로젝트

알고리즘 학습 문제 풀이

문제

모든 테스트 케이스에서 최대 이익을 낼 수 있는 계산을 하는 알고리즘

1,000,000일 동안 10,000의 가격으로 매일 사게 되면 100,000,000,000 이 되므로 int형으로 불가능 long 사용

이해 및 접근

일단, 처음에 접근한 방식은 가격이 '3 5 9' 일 때 이틀 동안 한 개씩 사서 마지막날 팔면 되겠다. 라고 생각했다. 하지만 항상 가격이 오르지 않을 경우도 존재하기에 이러한 방식은 오답이다.
다른 사람의 풀이법을 보다가 주식 차트처럼 그래프화하여 푸는 방식에 영감을 받아 풀 수 있었다.

그래서 모든 날들의 가격을 뒤에서 부터 생각하여, 최고가를 max라는 변수에 저장하고 하루씩 전날이 될 때마다 값을 비교하여 최고가였을 때보다 가격이 저렴하면 무조건 구매하게 되어 수익이므로 max - '당일가격' 으로 계산하고 모든 날을 반복하며 값을 최종적으로 더한 값이 최대 이익 값이 된다.

풀이

public class Swea {
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);

        int T = sc.nextInt();

        for (int test_case = 1; test_case <= T; test_case++) {
            int N = sc.nextInt();
            int[] arr = new int[N];


            for (int i = 0; i < N; i++) {
                arr[i] = sc.nextInt();
            }

            long profit = 0;
            int max = 0;
            for (int j = N - 1; j >= 0; j--) {
                int today = arr[j];
                if (max > today) {
                    profit += max - today;
                }
                else {
                    max = today;
                }
            }
            System.out.println("#" + test_case + " " + profit);
        }
    }
}