[SWEA D2] 1859. 백만 장자 프로젝트 .py

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

SW Expert Academy

문제

25년 간의 수행 끝에 원재는 미래를 보는 능력을 갖게 되었다. 이 능력으로 원재는 사재기를 하려고 한다.

다만 당국의 감시가 심해 한 번에 많은 양을 사재기 할 수 없다.

다음과 같은 조건 하에서 사재기를 하여 최대한의 이득을 얻도록 도와주자.

1. 원재는 연속된 N일 동안의 물건의 매매가를 예측하여 알고 있다.
2. 당국의 감시망에 걸리지 않기 위해 하루에 최대 1만큼 구입할 수 있다.
3. 판매는 얼마든지 할 수 있다.

• 입력

첫 번째 줄에 테스트 케이스의 수 T가 주어진다.

각 테스트 케이스 별로 첫 줄에는 자연수 N(2 ≤ N ≤ 1,000,000)이 주어지고,

둘째 줄에는 각 날의 매매가를 나타내는 N개의 자연수들이 공백으로 구분되어 순서대로 주어진다.

각 날의 매매가는 10,000이하이다.

• 출력

각 테스트 케이스마다 ‘#x’(x는 테스트케이스 번호를 의미하며 1부터 시작한다)를 출력하고, 최대 이익을 출력한다.

ex

3일간의 매매가 -> 1, 2, 3 : 처음 두 날에 원료를 구매하여 마지막 날에 팔면 3의 이익을 얻을 수 있다.

3일간의 매매가 -> 10 7 6: 아무 것도 사지 않는 것이 최대 이익이다.
3일간의 매매가 -> 3 5 9: 1,2일에 각각 한 개씩 사서 세 번째 날에 두 개를 팔면 10의 이익을 얻을 수 있다.

Solution

앞으로의 매매가중에 가장 큰값을 만나면 큰 값 전의 모든 숫자를 읽어오는게 고민이었다. 문제는 주어진 day동안 1번만 파는 것이 아니라는 것. 인덱스 0으로 시작하며 검사하는 것보다 뒤에서부터 검사하는 것이 이해하기 편하여 거꾸로 진행하였다.

T = int(input())

for test_case in range(1, T + 1):
    day = int(input())
    prices = list(map(int, input().split()))
    answer = 0

    max_price = prices[-1] 
    
    for i in range(day-2, -1, -1):
        if prices[i] > max_price:
            max_price =prices[i]
        else:
            answer += max_price - prices[i]


    print(f'#{test_case} {answer}')