[SWEA] #1859 백만 장자 프로젝트.python(파이썬)

문제 링크 / 출처

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5LrsUaDxcDFAXc&categoryId=AV5LrsUaDxcDFAXc&categoryType=CODE&problemTitle=1859&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1

SW Expert Academy

 

문제요약

사재기를 했을 때 얻을 수 있는 최대의 이익을 계산하는 문제.

[제약 사항]

1. N일 동안의 물건의 매매가를 예측하여 알고 있다.
2. 하루에 최대 1만큼 구입할 수 있다.

판매는 얼마든지 할 수 있다.

• 2 ≤ N ≤ 1,000,000
• 각 날의 매매가는 10,000이하

 

풀이

구매는 하루에 한번만 가능하고 판매에는 제약사항이 없으므로

 

가장 큰 이익을 얻기 위해서는 매일매일 구매한 후 최댓값이 되는 시점에서 판매해야한다.

 

최대값 이후의 시점에서는 다시 최대값이 되는 시점에서 판매해야한다.

 

즉, 현재시점 이후의 최대값에서 판매해야하므로 뒤에서 부터 탐색하며,

 

최댓값을 갱신해나가면서 이익만을 계산해서 추가해주어 풀이했다.

 

코드

T = int(input())

for tc in range(1, T+1):
    N = int(input())
    prices = [int(i) for i in input().split()]

    max_price = prices[-1]
    result = 0

    # 가장 큰 이익을 얻기 위해서는 리스트에서 현재위치 이후에 나오는 최댓값에 판매해야하므로,
    for i in range(len(prices)-1, -1, -1): # 뒤에서부터 탐색
        price = prices[i]

        if max_price < price:
            max_price = price

        result += max_price - price # 이익만큼 결과에 추가, 

    print('#{} {}'.format(tc, result))