문제

25년 간의 수행 끝에 원재는 미래를 보는 능력을 갖게 되었다. 이 능력으로 원재는 사재기를 하려고 한다.

다만 당국의 감시가 심해 한 번에 많은 양을 사재기 할 수 없다.

다음과 같은 조건 하에서 사재기를 하여 최대한의 이득을 얻도록 도와주자.

1. 원재는 연속된 N일 동안의 물건의 매매가를 예측하여 알고 있다.
2. 당국의 감시망에 걸리지 않기 위해 하루에 최대 1만큼 구입할 수 있다.
3. 판매는 얼마든지 할 수 있다.

예를 들어 3일 동안의 매매가가 1, 2, 3 이라면 처음 두 날에 원료를 구매하여 마지막 날에 팔면 3의 이익을 얻을 수 있다.

입력

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

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

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

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

출력

각 테스트 케이스마다 ‘#x’(x는 테스트케이스 번호를 의미하며 1부터 시작한다)를 출력하고, 최대 이익을 출력한다.

---

풀이

접근법

뒤에서부터 순회하며 작은 값이 나오면 차를 더하기

1. 가장 뒤에 있는 매매가를 현재 최댓값으로 저장
2. 매매가의 뒤에서부터 순회하며
   a. 최댓값보다 작은 값이 나오면 최댓값과 해당 매매가의 차를 sum에 더하기
   b. 최댓값보다 큰 값이 나오면 최댓값을 갱신

내가 접근했다가 포기한 방법!

1. 매매가가 증가하는 범위 저장
2. 감소하면 직전 범위의 마지막 값에서 이전 값들을 빼서 sum에 더하기

---

문제점

• 모든 값이 1 2 3 4 2 3 4 5 3 4 5 처럼 계속 증가하다가 한 번 감소하는 형태가 아님
• 이중for문이 필요하기에 시간복잡도 증가 등등

코드

package 백만장자프로젝트_1859;

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

public class Solution {

	public static void main(String[] args) throws NumberFormatException, IOException {
		/*
		 1. 원재는 연속된 N일 동안의 물건의 매매가를 예측하여 알고 있다.
    	 2. 당국의 감시망에 걸리지 않기 위해 하루에 최대 1만큼 구입할 수 있다.
    	 3. 판매는 얼마든지 할 수 있다.
		 */
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		int T = Integer.parseInt(br.readLine());
		
		for (int t = 1; t <= T; t++) {
			
			int days = Integer.parseInt(br.readLine()); // 며칠?
			long[] prices = new long[days]; // 매매가 배열
			
			st = new StringTokenizer(br.readLine());
			for (int d = 0; d < days; d++) {
				prices[d] = Long.parseLong(st.nextToken());
			}
			
			
			// 계산하기
			long ans = 0;
			long currMax = prices[days-1];
			for (int i = days-2; i >= 0; i--) { //뒤에서부터 확인
				if (prices[i] < currMax) {
					ans += (currMax - prices[i]);
				}
				currMax = Math.max(currMax, prices[i]); // 최댓값 확인
				
			}
			
			System.out.println("#" + t + " " + ans);
			
			
		}
	}

}

🌟 핵심 포인트

1. test case의 값들이 굉장히 크다! >> int 대신 long 사용하기 <<
2. 앞에서부터 순회하는 것보다 뒤에서부터 순회하는 것이 훨씬 쉽고 빠르다!