[백준] 11501 주식

백준 11501 주식 문제 바로가기

 

간단히 말해, 날짜별 주식 가격이 주어져있을때 최대 이익을 구하는 문제이다. 단, 할 수 있는 행동은 아래와 같다.

1. 주식 하나를 산다.
2. 원하는 만큼 가지고 있는 주식을 판다.
3. 아무것도 안한다.

처음 풀이

- 오늘 주식 가격과 내일 주식 가격을 비교했을때 내일이 더 높다면 오늘자 주식을 산다.
- 오늘 주식 가격과 내일 주식 가격을 비교했을때 내일이 더 낮다면 이전에 산 주식이 있을경우 판다.

import sys  
input=sys.stdin.readline  

T = int(input())  

for \_ in range(T):  
    N = int(input())  
    stocks = list(map(int, input().split()))  
    count = 0  
    totalPrice = 0  
    stocks.append(0)  
    for i in range(len(stocks)):  
        if stocks\[i\] == 0:  
            break  
        if stocks\[i\] <= stocks\[i+1\]:  
            totalPrice += -stocks\[i\]  
            count += 1  
        else:  
            totalPrice += (stocks\[i\] \* count)  
            count = 0  
    print(totalPrice)  

stocks 배열의 마지막에 0을 append 한 이유는 마지막 날인지 판단하기 위해서 넣어주었다...

 

역시, 제출하자마자 틀렸다! 이 알고리즘이 맞을거라 생각했는데 stocks=[1, 2, 1, 100]인 경우 첫째날에 내일 가격이 오른다고 사고, 둘째날에 내일 가격이 내려간다고 팔고, 셋째날에 내일 가격이 오른다고 사게되면 -1+(2x1)-1+(100x1) = 100이지만, 첫째, 둘째, 셋째날 모두 산다면 -1-2-1+(100x3) = 296으로 더욱더 이득이란것을 알 수 있었다. 따라서 내일 가격이 오른다고 오늘 주식을 사고, 내일 가격이 떨어진다고 이미 사둔 주식을 팔아버리는 알고리즘은 애초에 틀린 생각이었다.

 

그럼 어떻게?

잘 생각해보자 실제로 문제에 오늘부터 미래까지의 주식 가격이 주어져있긴 하지만, 앞에서부터 하나씩 탐색하다보면 결국 미래에는 어떤 가격이 있을지 모른다. 미래를 알고있다는 능력(문제 조건)에 집중하여 이것을 사용해보자. 미래를 알고 있으니까 미래에서부터 현재로 되돌아오면 되지 않을까?

1. 미래의 날짜부터 거꾸로 주식의 가격을 탐색한다.
2. 현재의 주식 가격이 이전에 기록되어 있던 최대 가격(maxStockPrice)보다 작다면 차익을 계산한다.
3. 그렇지 않다면 이전 최대 가격(maxStockPrice)을 현재의 가격으로 갱신한다.

이렇게 차익을 계속 계산하다보면 최종적인 이익이 나오게된다.

import sys  
input=sys.stdin.readline  

T = int(input())  

for \_ in range(T):  
    N = int(input())  
    stocks = list(map(int, input().split()))  
    totalStockPrice = 0  
    maxStockPrice = 0  

    for i in range(len(stocks)-1, -1, -1):  
        if stocks\[i\] > maxStockPrice:  
            maxStockPrice = stocks\[i\]  
        else:  
            totalStockPrice += maxStockPrice - stocks\[i\]  

    print(totalStockPrice)  

 

정리

가끔은 반대로도 생각해보자