[SWEA] 1859번 백만장자 프로젝트

문제

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

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

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

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

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

---

[TC1]

입력: 3 5 9

정답: 10

풀이: 첫째, 둘째 날 물건을 구입해서 셋째 날에 팔면 6 + 4 = 10의 이익을 낼 수 있다.

 

[TC2]

입력: 10 7 6

정답: 0

풀이: 날짜가 지날 수록 가격이 줄어드므로 구매를 하지 않는다.

 

[TC3]

입력: 1 1 3 1 2

정답: 5

풀이: 첫째, 둘째날에 물건을 사서 셋째 날에 팔고, 넷째 날에 물건을 사서 다섯째 날에 팔면 (3 - 1) + (3 - 1) + (2 - 1) = 5의 이익이 난다.

내 생각

max 값의 인덱스를 구한 뒤 그 인덱스까지의 원소들을 더하고 price = price[index:] 를 통해 배열을 잘라줬다.

테스트케이스는 통과했지만 런타임 에러가 떳다.

def get_profit(arr):
    profit = 0
    max_price = max(arr)
    for j in range(arr.index(max_price)):
        profit += (max_price - arr[j])
    return profit

t = int(input())
answer = []
for i in range(t):
    n = int(input())
    price = list(map(int,input().split()))
    a = 0
    while len(price) > 1:
        if price.index(max(price)) > 0:
            a += get_profit(price)
        price = price[price.index(max(price))+1:]
    answer.append(a)

for i in range(t):
    print('#{} {}'.format(i+1,answer[i]))

풀이

배열의 맨 뒤 원소부터 비교하며 max값을 갱신해주면 된다. 

t = int(input())
answer = []
for i in range(t):
    n = int(input())
    price = list(map(int,input().split()))
    max_price = 0
    a = 0
    for j in range(len(price)-1,-1,-1):
        if price[j]>max_price:
            max_price=price[j]
        else:
            a += (max_price-price[j])
    answer.append(a)

for i in range(t):
    print('#{} {}'.format(i+1,answer[i]))