[Python, 파이썬] SWEA 1859. 백만 장자 프로젝트

각 날의 매매가들이 주어질 때, 사재기를 해서 얻을 수 있는 최대 이익을 구하는 문제다

 

 

1. 원재는 연속된 N일 동안의 물건의 매매가를 예측하여 알고 있다.

2. 당국의 감시망에 걸리지 않기 위해 하루에 최대 1만큼 구입할 수 있다.

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

 

 

T = int(input()) # 테스트 케이스 T

for i in range(1, T+1):
    x = int(input()) # 매매가 개수 x
    case = list(map(int, input().split())) # 매매가 N

    sell = x-1 # 판매가
    money = 0 # 얻은 이익을 저장

    for i in range(x-1, -1, -1):

        if(case[sell] > case[i]):
            money += (case[sell] - case[i]) # 매매가보다 작으면 판매

        else:
            sell = i # 현 매매가보다 크면 업뎃
            
        
    
    print("#%d %d" %(i+1, money))

 

 

 

[문제풀이]

---

 

마지막 날을 처음 판매값으로 설정하고 뒤에서부터 시작.

더 높은 가격이 발견될 시 새로운 판매값으로 업데이트하고 낮은 가격일땐 차액을 더하면 된다.