SWEA D2 1859. 백만 장자 프로젝트 (python)

백만 장자 프로젝트

 

풀이

연속된 N일 동안 물건의 매매가를 알고 있고, 이를 이용해 미리 사고파는 작업을 하려 한다.
당국의 감시망에 걸리지 않기 위해 1만큼 구입하고, 판매는 구매 후 언제든 가능.

원재가 얻을 수 있는 최대이익을 구하도록 하자.

몇 가지 방법을 했었는데, 제한시간 초과로 통과하지 못했었다.
앞에서 하는 방법 때문에 문제가 있나 싶어서 뒤에서부터 검사하기로 했다.

1. 우선 반복문으로 모든 일자를 역순으로 돌았다.
2. 이때 가장 큰 값을 찾아내며 돌았고, 만약 가장 큰 값인 max_value보다 이번 일자의 값이 더 작다면 그것을 이득으로 계산하기로 했다.

이러니 시간 초과 없이 해결되었다.

T = int(input())
for testcase in range(1,T+1):
    earn = 0
    days = int(input())
    days_list = list(map(int, input().split()))

    max_value = 0
    for i in range(len(days_list)-1, -1, -1):
        if days_list[i] > max_value:
            max_value = days_list[i]
        else:
            earn += max_value - days_list[i]
    print(f'#{testcase} {earn}')

25년간의 수행 끝에 미래를 보는 능력으로 사재기라니..... 당황스럽다.