[swea] 1859. 백만장자 프로젝트

문제 바로가기

• 난이도 : D2

t = int(input())

for i in range(t):
    N = int(input())
    result = 0
    prices = list(map(int, input().split()))
    max_price_idx = prices.index(max(prices))
    if max_price_idx == 0:
        pass
    elif max_price_idx == N-1:
        for i in range(N-1):
            result += prices[N-1] - prices[i]
    else:
        while prices:
            max_price_idx = prices.index(max(prices))
            for i in range(max_price_idx):
                result += prices[max_price_idx] - prices[i]
            prices = prices[max_price_idx+1:]
    print(f"{i+1} {result}")

가장 높은 매매가의 인덱스를 저장한다. 가장 높은 매매가 전까지는 무조건 사는것이 이득이다.

따라서 가장 높은 인덱스가 0일때, 마지막일때, 나머지로 나누어 풀었다.

우선 인덱스가 0일때는 이득을 볼 수 있는 경우가 없다. 따라서 결과는 0

인덱스가 마지막일때는 다 사서 마지막에 팔면 최대의 이익을 얻게된다.

나머지일때는 가장 높은 인덱스 전까지 사서 가장 높은 값에 팔고 지나친 인덱스들은 리스트에서 삭제하고 새로운 가장 높은 인덱스를 구하여 이를 리스트의 요소가 빌 때까지 반복하였다.