[백준 11501번] 주식

11501번: 주식

t = int(input())

for _ in range(t):
    n = int(input())
    prices = list(map(int,input().split()))

    answer = 0

    maximum = prices[-1]

    for i in range(n-2,-1,-1):
        if prices[i] > maximum:
            maximum = prices[i]
        elif prices[i] < maximum:
            answer += (maximum - prices[i])
    
    print(answer)

    # 시간 초과 코드
    # stock = 0
    
    # for i,price in enumerate(prices):
    #     maximum = max(prices[i:])

    #     if maximum == price:
    #         answer += (price*stock)
    #         stock = 0
        
    #     elif price < maximum:
    #         answer -= price
    #         stock += 1

 

이번 문제는 모든 날의 주가를 안다는 가정 하에, 매일 주식을 사거나 원하는 만큼 팔거나 아무것도 안할 수 있을 때 얻을 수 있는 최대 이익을 구하는 문제이다.

 

미래의 가격을 알고 있고, 주식이라는 것은 싸게 구매해서 최대한 비싸게 파는 방식으로 수익을 낼 수 있으므로

1. 현재 가격이 미래 가격보다 싸면 사고,

2. 미래 가격보다 비싸면 아무것도 하지 않고,

3. 지금 가격이 최대 가격이면 팔면 된다.

 

따라서

1. 현재 이후의 가격의 최대값을 구하고,

2. 현재 가격이 최대값보다 싸면 사고,

3. 최대값이 됐을 때 팔면 된다.

 

하지만 위 방식 시간 초과 코드와 같이 그대로 풀이하게 되면 최댓값을 구하는 max 함수로 인해 O(N^2)의 시간복잡도가 발생하여 제한시간 5초보다 훨씬 많은 시간이 소요되어 시간초과가 발생하게 된다.

 

따라서 최댓값을 구하는 연산을 수행하지 않기 위해 마지막 값(prices[-1])을 최댓값으로 셋팅한 뒤 n-2번째부터 역순으로 순회하며 최댓값보다 큰 경우에는 최댓값을 갱신시켜주고, 최댓값보다 작은 경우에는 얻은 수익(최댓값 - 현재 가격)을 더해주는 방식으로 풀이하면 제한시간 내에 풀이할 수 있다.

 

모의 코딩테스트 3문제 중 이 문제만 풀이하지 못했는데, 아무래도 주식을 해본 적이 없어서 위와 같은 원리가 익숙하지 않아서 그런지 바로 풀이하지 못하였다. 탐욕 알고리즘 문제도 자주 연습해 보아야겠다 .. :)