[알고리즘][백준] 11501. 주식

문제

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

 

 

 

문제 아이디어

1	5	8	15	4	7	8	3	6

 

위와 같이 1, 5, 8, 15, 4, 7, 2, 3, 2 가 있다고 생각해 봅시다. 여기서 최대로 팔아먹으려면 최대한 큰 비용일 때 팔아야 되는데,

 

1. 예를 들어 맨 처음 1, 5, 8 은 15일 때 가장 비싸게 팔릴 것입니다.
2. 15는 언제 팔아도 비쌀 수가 없죠. 자신이 가장 비싸거든요. 안 사는게 이득입니다.
3. 4와 7은 8일 때 가장 비싸게 팔립니다.
4. 8은 해봐야 자기 자신일 때 밖에 없습니다. 역시 안 사는게 이득입니다.
5. 3은 6일 때 가장 비싸게 팔립니다.
6. 6도 안 사는게 이득입니다.

즉 주식을 산 시점부터 뒤를 탐색하면서 가장 비쌀 때 파는게 이득이라는 얘긴데, 위의 표를 보고 가장 이득이 크게끔 판매하기 위해서 아래 표로 정리하면 다음과 같습니다. 

1	5	8	15	4	7	8	3	6
15	15	15	15	8	8	8	6	6

 

결국 뒤에서부터 쭉 탐색하면서 가장 큰 값으로 업데이트하면 되는 문제였습니다!

import sys
imput = sys.stdin.readline

T = int(input())

for t in range(T):
    N = int(input())
    li = list(map(int, input().rstrip().split()))

    mx = [0 for _ in range(N + 1)]
    currMx = 0
    sum = 0
    for idx, value in enumerate(li[::-1]):
        # print(idx, value)
        currMx = max(value, currMx)
        mx[idx] = currMx
    
    mx.reverse()
    mx.pop(0)
    
    for n in range(N):
        sum += mx[n] - li[n]

    print(sum)