문제

BOJ 11501: 주식 https://www.acmicpc.net/problem/11501

풀이

조건

• 아래 세 가지 중 한 행동을 한다.
  • 주식 하나를 산다.
  • 원하는 만큼 가지고 있는 주식을 판다.
  • 아무것도 안한다.
• 최대 이익이 얼마나 되는지 계산한다.

풀이 순서

• 더 미래의 날짜부터 거꾸로 주식의 가격을 탐색한다.
  • 앞에서부터 탐색한다면 미래에 어떤 가격이 있을지 모르기 때문이다.
• 현재의 주식 가격이 현재 기록되어 있는 최대 가격보다 작다면 차익을 실현한다.
• 그렇지 않다면 현재 최대 가격 기록을 현재의 가격으로 갱신한다.

코드

T = int(input())

for t in range(T):

    N = int(input())
    price = list(map(int, input().split()))

    money = 0 # 이익

    maxPrice = 0 # 주식의 최대 가격
    for i in range(len(price)-1, -1, -1):
        if price[i] > maxPrice:
            maxPrice = price[i]
        else: # 현재 가격이 현재 최대 가격보다 작다면 차익 실현
            money += maxPrice - price[i]

    print(money)

정리

• 순차적이 아니라 반대로 생각해보는 것도 해봐야겠다.