SWEA 1859번: 백만 장자 프로젝트 (D2) - Python 풀이

문제 설명

SW Expert Academy

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

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

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

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

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

[입력]

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

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

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

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

[출력]

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

[예제 풀이]

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

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

입력

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

출력

#1 0
#2 10
#3 5

풀이 과정

매매가 중 최댓값이 나오기 전까지는 매일 1개씩 사고, 최댓값일 때 팔아야 최대 이익을 얻을 수 있습니다.

그렇기 때문에 매매가를 담은 배열에서 최댓값과 최댓값의 인덱스를 찾습니다.

최댓값의 인덱스가 0이면 그 앞에서는 물건을 구매하지 않았을 테니 잘라서 없애 버리고, 인덱스 1부터 다시 최댓값을 구합니다.

0이 아니면, 맨 앞에서 최댓값 전까지 슬라이싱 해서 합계를 구합니다. 이게 내가 구매한 물건의 가치 총합이 됩니다. 이 값을 최댓값이 뜬 날에 모두 판매를 했을 테니

얻은 이익 = (매매 최댓값 * 구매한 물건의 개수) - 구매한 물건의 가치 총합

위의 식을 계산하여 이익을 구할 수 있습니다.

모든 매매가를 확인할 때까지 위의 과정을 반복하여 얻은 이익을 누적하면 답이 됩니다.

정답 코드

T = int(input())

for test_case in range(1, T + 1):
    answer = 0
    # 매매가 개수
    N = int(input())
    # 매매가 입력값 저장
    prices = list(map(int, input().split()))
    # 구매한 물건의 개수
    count = 0
    # 구매한 물건의 가치 총합
    buying_price_sum = 0
    # prices 배열이 빌 때까지 반복
    while prices:
        # 매매가의 최댓값 구하기
        max_value = max(prices)
        # 최댓값의 인덱스 구하기
        idx = prices.index(max_value)
        # 최댓값의 위치가 맨 왼쪽이 아니면
        if idx != 0:
            # 앞서 idx개만큼 물건을 구매했을 테니 idx가 구매한 물건의 개수와 같다
            count = idx
            # 인덱스 0부터 최댓값 인덱스 직전까지의 매매가 합을 구한다 
            buying_price_sum = sum(prices[:idx])
            # 매매 최댓값일 때 팔아서 얻은 이익 = (최대 매매가 * 구매한 물건의 개수) - (구매한 물건의 가치 총합)
            answer += (max_value * count) - buying_price_sum
        # 최댓값 이후만 잘라서 prices 배열 업데이트
        prices = prices[idx+1:]
    print("#%d %d" %(test_case, answer))

이상입니다.