[BOJ/Greedy] 백준 11501 - 주식 (Java)

백준 11501 - 주식

https://www.acmicpc.net/problem/11501

문제

3가지 중 한 행동을 함
1. 주식을 산다
2. 원하는 만큼 가지고 있는 주식을 판다
3. 아무 것도 안한다

=> 날 별로 주식의 가격을 알려줬을 대, 최대 이익이 얼마나 되는지?
ex. 날 수: 3일/ 날 별로 주가: 10, 7, 6 -> 주가가 계속 감소 => 최대 이익: 0
주가: 3, 5, 9 -> 처음 두 날에 주식을 하나씩 사고, 마지막날 다 팔아 버리면 이익: 10

입력
첫 줄: 테스트케이스 수 T
각 테스트케이스 별로 첫 줄에는 날의 수를 나타내는 N (2 <= N <= 1,000,000)
둘째 줄: 날 별 주가를 나타내는 N개의 자연수들 (공백, 날 별 주가 <= 10,000)
출력
각 테스트케이스 별로 최대 이익을 나타내는 정수 출력
부호 있는 64-bit 정수형으로 표현 가능

---

풀이

미래의 최고가를 기준으로 판단 -> 미래를 기준으로 현재를 바라봐야 함

=> 뒤에서부터 순회

int max = arr[N - 1];
long result = 0;
for (int i = N - 2; i >= 0; i--) {
	if (arr[i] < max) result += max - arr[i];
	else max = arr[i];
}

• 현재가격 < `max`
  • 그날에 사고, `max`에 팜 => 이익: `max - arr[i]`
• 현재가격 >= `max`
  • 그 날이 새로운 최고가 => `max` 갱신

---

예시

• 10 7 6 / max = 6
  • 7 > 6 -> max = 7
  • 10 > 7 -> max = 10
  • => 이익 X
• 3 5 9 / max = 9
  • 5 < 9 -> 9 - 5 = 4
  • 3 < 9 -> 9 - 3 = 6
  • => 이익: 4 + 6 10
• 1 1 3 1 2 / max = 2
  • 1 < 2 -> 2 - 1 = 1
  • 3 > 2 -> max = 3
  • 1 < 3 -> 3 - 1 = 2
  • 1 < 3 -> 3 - 1 = 2
  • => 이익: 1 + 2 + 2 = 5

---

코드

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

// 주식
public class boj_11501 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int T = Integer.parseInt(br.readLine());
        while (T-- > 0) {
            int N = Integer.parseInt(br.readLine());
            int[] arr = new int[N];

            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int i = 0; i < N; i++) {
                arr[i] = Integer.parseInt(st.nextToken());
            }

            int max = arr[N - 1];
            long result = 0;
            for (int i = N - 2; i >= 0; i--) {
                if (arr[i] < max) result += max - arr[i];
                else max = arr[i];
            }

            sb.append(result).append("\n");
        }

        System.out.println(sb);
    }
}