테페리넷

이 문서는 읽기 전용입니다. 원본을 볼 수는 있지만 바꿀 수는 없습니다. 문제가 있다고 생각하면 관리자에게 문의하세요.
====== 주식 ======

===== 풀이 =====
  * 가장 큰 이익을 보는 방법은, 매일 주식을 사고, x번째 날에 산 주식을 x번째날 이후에 가장 가격이 비싼 날에 파는 것이다.
  * 하지만, 모든 x에 대해서 x번째날 이후에 가장 가격이 비싼 날을 구하는 것은 비효율적이다.
  * a0(=전체 구간에서 가장 가격이 비싼날)을 찾고, a1(=a0 이후에서 가장 가격이 비싼날). a2,..., ax를 구한 뒤에, (0,a1)까지의 주식은  a1날에 팔고, (a1,a2) 까지의 주식은 a2에 팔고, .. 하는 방법이 가능하다. 하지만 a_i를 찾을때, a1을 구하고, 남은 구간에서 a2를 구하고 하는 식으로 찾으려고 하면 O(n^2)이 걸린다.
  * 더 효율적인 방법은 뒤에서부터 이터레이션을 하면서 a_x, a_x-1, ..., a1 을 역순으로 찾는 것이다. a_x, a_x-1, ..., a1를 다 갖고 있을 필요도 없고, 그냥 최고 가격을 유지하면서 있으면서, 현재 가격이 최고 가격보다 작으면 그 차액만큼을 더해주고, 최고 가격보다 크면 최고가격을 갱신해주는 식으로 처리하면 된다. 이렇게 하면 O(n)에 계싼이 가능하다.

===== 코드 =====
<dkpr py>
"""Solution code for "BOJ 11501. 주식".

- Problem link: https://www.acmicpc.net/problem/11501
- Solution link: http://www.teferi.net/ps/problems/boj/11501

Tags: [Greedy]
"""


def main():
    T = int(input())
    for _ in range(T):
        N = int(input())  # pylint: disable=unused-variable
        prices = [int(x) for x in input().split()]

        answer = 0
        max_price = 0
        for price in reversed(prices):
            if price <= max_price:
                answer += max_price - price
            else:
                max_price = price

        print(answer)


if __name__ == '__main__':
    main()
</dkpr>

{{tag>BOJ ps:problems:boj:실버_2}}