[BOJ] 주식

코드

import sys
# from collections import deque
input = sys.stdin.readline

for _ in range(int(input())):
    days = int(input())
    prices = list(map(int, input().split()))
    
    max_price = max(prices)
    quantity = 0    # 보유 주식 수
    profit = 0    # 수익

    # marr[i] = i일 이후 주식 가격의 최대값
    marr = [0]*days
    marr_max = prices[-1]
    for i in range(days-1, -1, -1):
        marr[i] = marr_max
        if prices[i] > marr_max:
            marr_max = prices[i]

    for i in range(days):
        if prices[i] < max_price:
            profit -= prices[i]
            quantity += 1
        if prices[i] == max_price:
            profit = profit + quantity * max_price
            quantity = 0
            max_price = marr[i]

    print(profit)

결과

풀이 방법

• 주식 가격 추이를 미리 알고 있으므로, 가격이 낮을 때 사고 가장 고점에서 지금까지 샀던 것을 모두 팔아야 한다.
• 예를 들어 1 1 3 1 2 이면 1 1 일때 사서 3에 팔고, 그다음 1일때 사서 2에 팔면 최대 수익이다.
• 따라서 오늘(i일) 이후의 주식 가격의 최대값을 미리 marr 배열에 계산해놓고, 고점인 날이 올 때까지는 사고, 고점인 날에 보유 주식 개수(quantity)만큼 팔도록 구현했다.
• 고점에서 팔 때마다 다음 고점을 max(prices[i+1:]) 로 계산하면 시간초과가 나서 미리 i일 이후의 주식 가격을 계산해놓아야 풀렸다.