백준 11501번 Python / Greedy

문제풀이 GitHub

https://github.com/Seokii/baekjoon

GitHub - Seokii/baekjoon: Daily Commit for Baekjoon

 

문제 링크

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

11501번: 주식

 

풀이

t = int(input())

for _ in range(t):
    n = int(input())
    prices = list(map(int, input().split()))
    max_price = 0
    answer = 0
    for i in range(len(prices)-1, -1, -1):
        if max_price < prices[i]:
            max_price = prices[i]
        elif max_price > prices[i]:
            answer += (max_price - prices[i])
    print(answer)

처음엔 for문으로 순회하며 모든 경우의 수를 생각해보려고 했으나 아무래도 시간 초과가 발생할 것 같다는 생각이 들었습니다.

그래서, 생각하다가 리스트의 뒤쪽에서 순회를 하며 앞의 인덱스로 조회하면서 그 값이 더 작으면 기준 가격과의 차이를 전부 더해주면 되겠다는 생각을 했습니다.

max_price 변수가 기준 가격을 저장하는 변수이고,

answer 변수가 기준 가격에서 해당 인덱스의 가격과 비교해 조건이 성립할 때, 차를 구해 전부 합해 저장하는 변수입니다.

1 1 3 1 2 예제의 경우,

뒤에서부터 순회하기 때문에, 2가 처음 max_price 변수에 저장이 됩니다.

for문이 진행되어 1을 만나면 인덱스의 값이 더 작기 때문에 2 - 1 = 1의 값을 answer에 더해줍니다.

이후, 3을 만나면 인덱스 값이 더 크기 때문에 max_price를 3으로 지정하고 넘어갑니다.

이 과정을 반복해 답을 구했습니다.