[SWEA] 1859 : 백만 장자 프로젝트 (Python/파이썬)

문제 링크

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5LrsUaDxcDFAXc#none

문제

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

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

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

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

예를 들어 3일 동안의 매매가가 1, 2, 3 이라면 
처음 두 날에 원료를 구매하여 마지막 날에 팔면 3의 이익을 얻을 수 있다.

입력

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

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

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

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

출력

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

예제

입력

3
3
10 7 6
3
3 5 9
5
1 1 3 1 2

출력

#1 0
#2 10
#3 5

---

정답 및 풀이

T = int(input())

for tc in range(1, T + 1):
    n = int(input())
    prices = list(map(int, input().split()))

    max_price = 0   
    profit = 0

    for price in reversed(prices):
        if price > max_price:
            max_price = price
        else:
            profit += max_price - price

    print(f"#{tc} {profit}")

1. T = int(input())
   • 테스트 케이스의 개수를 입력받는다.
2. for tc in range(1, T + 1):
   • 테스트 케이스 수만큼 반복한다.
   • #1, #2, ... 형식의 출력을 요구하므로 1부터 시작한다.
3. n = int(input())
   • 각 테스트 케이스에서 주가 데이터의 개수를 입력받는다.
4. prices = list(map(int, input().split()))
   • 주가 데이터를 정수 리스트로 입력받는다.
5. max_price = 0
   • 미래의 최고 주가(매도 시점)를 저장할 변수다.
6. profit = 0
   • 누적 이익을 저장할 변수다.
7. for price in reversed(prices):
   • 주가를 뒤에서부터 탐색한다.
   • 미래의 가격을 먼저 보면서 이익을 계산하기 위함이다.
8. if price > max_price:
   • 현재 주가가 지금까지 본 최고가보다 크면, 새로운 최고 매도일로 갱신한다.
9. max_price = price
   • 최대 주가를 현재 주가로 변경한다.
10. else: profit += max_price - price
    • 현재 주가가 최고가보다 낮다면, 지금 사서 max_price일 때 팔면 얻는 이익을 계산해 더한다.
11. print(f"#{tc} {profit}")
    • 테스트 케이스 번호와 이익을 출력한다.