[Python] 백준 11501번: 주식

그리디를 이렇게도 적용할 수 있구나 싶은 문제여서 한번 정리해보려고 합니다.

주식에서 최대 이익을 내는 방법은 아래의 과정을 반복하는 것입니다.

1. 최대 주가에서 주식을 판다.
2. 그 이후의 주가들 중, 최대 주가에서 주식을 판다.
   ...

예를 들어 1, 3, 2, 5, 1, 4, 2, 3 로 주가가 움직인다면
다음과 같이 판매해야 합니다.

1, 3, 2, 5, 1, 4, 2, 3 : 5에서 주식을 판다
1, 3, 2, 5, 1, 4, 2 3 : 4에서 주식을 판다
1, 3, 2, 5, 1, 4, 2, 3 : 3에서 주식을 판다

따라서 앞에서부터 순회하며 maximum값을 구한다면, 뒤에 더 높은 주가가 있을 수 있어 여러 번의 반복문을 돌며 비교해주어야 하는 문제가 발생합니다.

하지만 뒤에서부터 순회하며 maximum값을 구한다면, 구한 maximum값에서 바로 주식을 판매하면 되므로 여러 번의 반복문을 돌지 않아도 됩니다.

이처럼 이러한 유형의 경우엔 뒤에서부터 그리디하게 최댓값을 취하는 풀이 방법을 사용하여 복잡도를 크게 줄일 수 있습니다.

t = int(input())
for _ in range(t):
    n = int(input())
    stocks = list(map(int, input().split()))
    money = 0
    max_stock = 0
    for i in range(n-1, -1, -1): # 뒤에서부터 순회
        if stocks[i] > max_stock:
            max_stock = stocks[i]
        else: 
            money += max_stock - stocks[i]
    print(money)