[SW Expert Academy] 1859. 백만 장자 프로젝트

SW Expert Academy 1859 문제 링크

SW Expert Academy

 

---

풀이

• 전체 경우의 매매가를 안다고 가정하였을 때 , 싸게 사서 비싸게 팔아 얻을 수 있는 최대 이익을 구하는 문제이다.
• 단순하게 가격을 뒤에서부터 읽으면서 max 값을 저장해놓고 , max값보다 싸면 그 max - 가격만큼 이익을 얻고 , max값보다 크다면 max값을 업데이트하면 된다.
• 코딩 테스트 스타일의 문제다 보니 10개의 테스트 케이스에 대해 30초를 제공한다.
• 단순히 따져보아도 1개의 테스트 케이스에 3초 걸리면 되니 , 시간은 여유 있는 편이다.
• 최대 1,000,000개의 입력이 주어지길래 당연히 sys.stdin.readline()을 사용하려 하였으나 , 채점 환경에서 sys가 사용불가로 나와 입력 부분을 모두 input()으로 처리하였다.

 

n = int(input())
for p in range(n):
    k = int(input())
    s = list(map(int, input().split(" ")))
    maxx = s[-1]
    ans = 0
    for i in range(len(s)-2,-1,-1):
        if s[i] < maxx:
            ans += (maxx-s[i])
        if s[i] > maxx:
            maxx = s[i]
    print("#%d %d" %(p+1 , ans))

---