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

접근 방법

뒤에서부터 최대값을 계산한다.

1 1 3 1 2 와 같은 경우를 예시로 들면 

i	value	max	calculate	profits
0	2	2	x
1	1	2	2 - 1 = 1	1
2	3	3	x
3	1	3	3 - 1 = 1	2
4	1	3	3 - 1 = 1	2

이렇게 된다.

배열을 뒤에서부터 탐색하면서 최대값을 갱신하고, 최대값보다 작은 경우라면 바로 이익을 계산해준다.

또한, N의 크기가 최대 1,000,000이고 각 날의 매매가는 10,000 이하이기 때문에 1,000,000번 최대 매매가를 더해준다 생각하면 10,000,000,000으로 int 자료형 범위를 넘어서기 때문에 합을 계산하는 변수는 long으로 설정했다.

 

코드

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

public class Solution_1859_백만장자프로젝트 {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer tokens;
		StringBuilder sb = new StringBuilder();

		int T = Integer.parseInt(br.readLine());

		for (int tc = 1; tc <= T; tc++) {
			sb.append("#").append(tc).append(" ");

			int N = Integer.parseInt(br.readLine());
			int[] arr = new int[N];

			int max = 0;
			long profits = 0;

			tokens = new StringTokenizer(br.readLine());
			for (int i = 0; i < N; i++) {
				arr[i] = Integer.parseInt(tokens.nextToken());
			}
			for (int i = N - 1; i >= 0; i--) {
				if(arr[i] > max)
					max = arr[i];
				else
					profits += max - arr[i];
			}
			sb.append(profits).append("\n");
		}
		System.out.println(sb);
	}
}

싸피 코테 치기 전에 풀어봤던 문제인데 다시 풀려니 헷갈려서 더 어렵게 생각했던 것 같다.

수학 들어가면... 🤢