방구석프로의 이야기

https://www.acmicpc.net/problem/11501

문제 해결을 위한 과정

이 문제의 경우 N이 1,000,000 이므로 일반적인 이중 for문으로는 해결할 수 없습니다. 그렇다면 한번 뒤집어보면 어떨까요?

각각의 테스트 케이스를 뒤집으면 다음과 같습니다.

6 7 10 -> 증가하는 경우는 따지지 않음

9 5 3 -> (9-5) + (9-3) = 10

2 1 3 1 1 -> (2-1) + (3-1) + (3-1) = 5

즉 뒤집으면 보다 쉽게 해결할 수 있음을 알 수 있습니다. 

뒤집어진 배열을 조회하면서 다음날의 주가가 더 낮다면 현재까지 있는 주가 중 최대 주가 - 다음날 주가를 더하면 쉽게 해결할 수 있습니다.

소스코드

T = int(input())
for t in range(T):
  n = int(input())
  arr = list(map(int, input().split()))
  revArr = arr[::-1]
  cost = revArr[0]
  ans = 0
  for i in range(1, len(revArr)):
    if cost < revArr[i]:
      cost = revArr[i]
    else:
      ans += (cost - revArr[i])
  print(ans)