BOJ 11501번: 주식

https://www.acmicpc.net/problem/11501

11501번: 주식

아이디어를 찾는 게 꽤나 어려웠던 문제이다.

처음에는 가격을 그래프로 그렸을 때 꼭짓점을 찾아서 꼭짓점의 앞에서 주식을 사고 꼭짓점에서 팔고, 또 계속 사다가 다음 꼭짓점에서 팔고 이런 식으로 하면 되지 않을까? 싶었지만 꼭짓점이 고점이 아닌 경우 해당 지점에서 주식을 매도하는 것보다 주식을 매수하는 게 더 이득이 크기 때문에 해당 접근 방식은 틀렸다.

 

단순하게 다시 생각해보니, 일단 가격의 고점을 찾고 고점 전까지는 매수만 하다가 고점에서 매도를 하면 최대 이득이 되는 거였다. 고점에서 매수를 한 이후에는 그 다음 날짜 중에서 고점을 다시 찾고 위의 과정을 반복하면 된다. 따라서 코드는 다음과 같다.

 

1. 주식 가격이 제일 높은 순서대로 내림차순 정렬을 한다. -> 이때 날짜(인덱스)도 알아야 하기에 파이썬의 `enumerate` 함수를 사용하여 입력받은 배열을 index와 value를 포함한 2차 배열로 만들어서 정렬을 했다.

2. 정렬한 배열을 순회하면서 해당 고점 날짜보다 이전의 날짜는 모두 매수하는 거라 생각하고 얻는 이득을 더한다. 이때 현재 고점의 날짜가 이미 계산이 완료된 날짜(before)보다 이후인 경우에만 실행되도록 한다. 

2-1. 계산을 완료한 후 before 값을 업데이트 한다. 10 9 7 처럼 가격이 계속 내려가는 경우도 있기 때문에 해당 코드는 앞선 if문과 관계없이 무조건 실행되도록 한다. 하지만 이미 지나간 날짜인 경우에는 업데이트 하면 안되기 때문에 조건을 걸어준다.

2-2. 계산한 날짜가 N과 같거나 넘어가면 조건문을 빠져나온다.

 

import sys
input = sys.stdin.readline

T = int(input())
for _ in range(T):
    N = int(input())
    arr = list(map(int, input().split()))
    sorted_arr = sorted(list(enumerate(arr)), reverse=True, key = lambda x : x[1])
    ans = 0
    before = 0
    for i in range(N):
        if (sorted_arr[i][0] > before):
            for j in range(before, sorted_arr[i][0]):
                ans += sorted_arr[i][1] - arr[j]
        if (before < sorted_arr[i][0] + 1):
            before = sorted_arr[i][0] + 1
        if (before >= N): break
    print(ans)