[백준 / Java] 11501 주식

문제

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

 

---

 

문제 개요

홍준이는 미래의 주식 가격을 정확히 예측할 수 있지만, 언제 어떤 방식으로 매매를 해야 최대 이익을 얻을지는 모른다.
매일 다음 세 가지 행동 중 하나를 할 수 있다.

• 주식을 하나 산다
• 가지고 있는 주식을 원하는 만큼 판다
• 아무것도 하지 않는다

주어진 날 별 주식 가격을 보고, 최대 이익을 계산하는 문제이다.

 

접근 방법

이 문제는 뒤에서부터 탐색하는 것이 핵심이다.

• 미래의 주가를 알기 때문에, "앞으로 가장 비싼 날"을 기준으로 현재 주가를 판단할 수 있다.
• 뒤에서부터 탐색하면서, 지금까지 본 주가 중 가장 높은 가격(max)을 기록한다.
• 현재 주가가 max보다 작으면, 지금 매수한 후 max 가격에 판매한다고 가정해 이익을 계산한다.
• 주가가 max보다 낮으면 이익 += (max - 현재가)를 해주고, 주가가 max보다 크면 max를 갱신하는 식으로 문제를 해결할 수 있다.

코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        init();
    }

    public static void init() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

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

            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < day; j++) arr[j] = Integer.parseInt(st.nextToken());

            trading(arr);
        }
    }

    public static void trading(int[] prices) {
        long earn = 0;  // 이익 (long형으로 해야 함: 최대 1_000_000 * 10_000)
        int max = 0; 

        // 뒤에서부터 탐색
        for (int i = prices.length - 1; i >= 0; i--) {
            if (prices[i] > max) {
                max = prices[i];  
            } else {
                earn += (max - prices[i]);
            }
        }

        System.out.println(earn);
    }
}