[Python] 백준 11501번 - 주식

1. 문제정보

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

11501번: 주식

 

2. 해결전략

리스트의 앞에서부터 탐색하면 알고리즘이 복잡해진다.. 구매한 날과 구매하지 않은 날을 구분하여 로직을 구현했었고 최가 가격을 갱신하면 구매하지 않은 날, 금액을 구매한 날과 구매한 금액으로 변환했다. 하지만 이 금액은 최고 금액이 중간에 나오는 경우 정상적으로 처리하지 못했다.

1시간 이상 해결을 못하다가 다른 분이 뒤에서 부터 리스트를 탐색하면서 쉽게 해결한 걸 보았다. 난 왜 이렇게 멍청한 거 같지..ㅠㅠ 다음에 다시 풀어봐야겠다..

 

3. 코드

# 실패코드

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

    buy_cnt = 0 # 매수한 날
    buy_price = 0 # 매수한 금액 
    no_buy_cnt = 0 # 매수하지 않은 날
    no_buy_price = 0 # 매수하지 않아 아낀 금액
    temp_price = 0
    max_price = prices[0] # 최고 가격
    for i in range(1, n):
        if max_price < prices[i]:
            # 최고가 갱신
            max_price = prices[i]

            # 전날의 주식을 매수한 것으로 처리
            buy_cnt += 1
            buy_price += prices[i-1]

            # 그동안 사지 않았던 주식을 샀던 것으로 처리
            buy_cnt += no_buy_cnt
            buy_price += no_buy_price

            # 사지 않았던 금액 초기화
            no_buy_cnt = 0
            no_buy_price = 0
            
            # 최고 가격에는 팔지 못한 금액
            temp_price = 0
        else:
            no_buy_cnt += 1
            no_buy_price += prices[i-1]

            # 최고 가격은 아니지만 전날보다 가격이 오른 경우
            if prices[i-1] < prices[i]:
                temp_price =+ (prices[i]-prices[i-1])

    print(buy_cnt*max_price - buy_price + temp_price)

 

# 성공코드

t = int(input())

for _ in range(t):
    n = int(input())
    prices = list(map(int, input().split()))
    
    current_price = prices[n-1]
    total_price = 0
    for i in range(n-2, -1, -1):
        if current_price > prices[i]:
            total_price += (current_price - prices[i])
        else:
            current_price = prices[i]
    print(total_price)