[SWEA] 백만 장자 프로젝트 - python

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5LrsUaDxcDFAXc&categoryId=AV5LrsUaDxcDFAXc&categoryType=CODE&problemTitle=%EB%B0%B1%EB%A7%8C&orderBy=SUBMIT_COUNT&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1

SW Expert Academy

 

처음에 푼 코드

시간초과가 발생해 다시 한 번 생각하며 생각했다. 

T = int(input())

for _ in range(T):
    n = int(input())
    arr = list(map(int, input().split()))

    profit = 0
    for i in range(n):
        tmp = 0
        maxtmp = 0
        for j in range(i+1,n):
            if arr[i] < arr[j]:
                tmp = arr[j]-arr[i]
                if maxtmp < tmp:
                    maxtmp = tmp
        profit += maxtmp
    print(f'#{_ + 1} {profit}')

 

 

처음엔 그리디로 해결하려다가 인덱스번호, 이것저것 저장해서 신경쓸게 많아서 단순하게 뒤에서부터 접근하니 문제가 쉽게 풀렸다.

 

T = int(input())

for _ in range(T):
    n = int(input())
    arr = list(map(int, input().split()))
    profit = 0
    tmp = arr[-1]
    for i in range(n-1, -1, -1):
        if tmp >= arr[i]:
            profit +=(tmp-arr[i])
        else:
            tmp = arr[i]

    print(f'#{_ + 1} {profit}')

 

완성