SWEA 1859 백만 장자 프로젝트 (python)

1859. 백만 장자 프로젝트 D2

 

참고문제

2021.04.20 - [Algorithm] - BOJ 11501 주식 (python)

문제

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

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

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

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

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

[입력]

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

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

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

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

[출력]

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

[예제 풀이]

1번째 케이스는 아무 것도 사지 않는 것이 최대 이익이다.

2번째 케이스는 1,2일에 각각 한 개씩 사서 세 번째 날에 두 개를 팔면 10의 이익을 얻을 수 있다.

풀이

T = int(input())
# 매도 타이밍을 잡는 함수
def sell_point(price, start_idx):
    # 초기 고점은 시작 포인트로 잡자
    max_price = price[start_idx]
    # 고점이 오는 날짜 역시 시작 날짜
    max_idx = start_idx
    # 이익은 일단 0
    total = 0
    # price를 검토해서 최대값 생성
    for i in range(start_idx, len(price)):
        if price[i] > max_price:
            max_price = price[i]
            max_idx = i
    # 고점까지 매일 1씩 산 이득을 계산
    for i in range(start_idx, max_idx):
        total += max_price - price[i]
    # 만약 장이 마감됐다면, 즉 시작점이 끝점까지 왔다면
    if start_idx == len(price)-1:
        # 이제 끝
        return 0
    # 내가 고점에서 물리게 될거라면
    if max_idx == start_idx:
        # 하루 쉬자, 즉 한칸 넘어가자
        return sell_point(price, max_idx+1)
    # 최고점까지의 이득을 챙기고 그다음 고점 검토를 해보자
    return sell_point(price, max_idx) + total

for tc in range(1, T+1):
    N = int(input())
    price = list(map(int, input().split()))
    result = sell_point(price,0)
    print("#{} {}".format(tc, result))