[swea] 1859. 백만 장자 프로젝트 / python 파이썬

thinking

어차피 물건은 마지막날에 팔기때문에 뒤에서부터 체크해주면 된다.

뭔말이냐면, 매매가가  3, 4,  3, 1, 2, 3,  1  인 경우

앞에  3, 4  는 4가 제일 크므로 4에서 팔고, 중간의  3, 1, 2, 3, 은 맨 뒤 3이 가장 크므로 3일 때 판다. 마지막  1  은 1일때 판다.

즉, 뒤에서부터 보면서 최대값을 구하고, 그 값보다 같거나 작은 애들의 수익을 더하면 된다.

 

코드

price 리스트의 뒤에서부터 최대값을 체킹할거라 max_val 을 맨 뒤의 값으로 잡아줬다.

맨 뒤부터 돌면서 값을 비교하고 갱신한다.

T = int(input())

for tc in range(1, T + 1):
    N = int(input())
    price = list(map(int, input().split()))
    revenue = 0

    max_val = price[-1]
    for i in range(N - 1, -1, -1):
        if price[i] >= max_val:
            max_val = price[i]
        revenue += max_val - price[i]

    print("#{} {}".format(tc, revenue))