문제

BOJ 11501, 주식

핵심

• 입력의 크기가 $10^6$이라 대략 $O(N\times\log_2N)$ 이하의 알고리즘을 사용한다.
• 날 별로 주식 가격이 주어지고 하루에 주식을 한 주를 사거나 모두 팔 수 있다. 최대 이익을 구해야 한다.
• 단순하게 생각하면 가격이 하락한다면 그 이전 가격으로 팔면 되지 않을까? 손해는 보지 않겠지만 최대 이익을 구할 수는 없다. 가격이 잠깐 하락해도 더 크게 상승할 수 있으니 최고 가격이 되기 전까지는 사는 게 이득이다. 만약 최고 가격에서 팔았다고 가정하면, 그다음 최고 가격은 어떻게 알 수 있을까? 최고 가격 배열을 만들고 가격이 하락할 때 그 이전 가격이 최고 가격일 때 팔면 된다. 하지만 이를 계산하기 위해서는 정렬하는 전처리 작업이 필요하고, 가격이 하락했을 때 최대 가격인지를 확인하고 최대 가격이라면 이를 제거하는 과정이 필요하다. 즉, 구현이 까다로워진다.
• 날 별로 주어지는 주식 가격을 뒤에서부터 보게 되면 해당 시점에서 미래 시점의 최대 가격을 알 수 있기 때문에 바로 최대 이익을 구할 수 있다. 미래 시점보다 해당 시점이 더 가격이 크다면 최대 가격을 갱신하면 된다.

개선

코드

시간복잡도

• $O(N)$

C++

#include <iostream>
using namespace std;

int prices[1'000'004];
int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int t;
	cin >> t;
	while (t--) {
		int n;
		cin >> n;
		long long ans = 0;
		for (int i = 0; i < n; ++i)
			cin >> prices[i];
		int mx = prices[n - 1];
		for (int i = n - 2; i >= 0; --i) {
			int now = prices[i];
			if (mx < now)
				mx = now;
			ans += mx - now;
		}
		cout << ans << '\n';
	}
}

Java

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

public class Main {
    static int[] prices = new int[1_000_004];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int t = Integer.parseInt(br.readLine());
        while (t-- > 0) {
            int n = Integer.parseInt(br.readLine());
            StringTokenizer st = new StringTokenizer(br.readLine());
            long ans = 0;
            for (int i = 0; i < n; i++)
                prices[i] = Integer.parseInt(st.nextToken());
            int mx = prices[n - 1];
            for (int i = n - 2; i >= 0; --i) {
                int now = prices[i];
                if (mx < now)
                    mx = now;
                ans += mx - now;
            }
            bw.write(ans + "\n");
        }
        bw.flush();
        bw.close();
        br.close();
    }
}