11501번: 주식
입력의 첫 줄에는 테스트케이스 수를 나타내는 자연수 T가 주어진다. 각 테스트케이스 별로 첫 줄에는 날의 수를 나타내는 자연수 N(2 ≤ N ≤ 1,000,000)이 주어지고, 둘째 줄에는 날 별 주가를 나타
www.acmicpc.net
코드
for _ in range(int(input())):
n = int(input())
lst = list(map(int, input().split()))
highest = -1
ans = 0
for i in range(n-1, -1, -1):
if highest < lst[i]:
highest = lst[i]
else:
ans += (highest-lst[i])
print(ans)
풀이는 간단하다.
날짜를 역순으로 가며 최대 주식 가격인 highest보다 낮은 가격이면 무조건 사들이고, highest보다 높은 가격이 나오면 highest를 그 값으로 수정해주면 된다.
거꾸로 진행하며 이전에 가장 높은 가격보다 낮은 가격은 매입하고, 더 높은 가격이 나오면 highest를 갱신하여 그 앞 날짜의 주식들은 새로운 highest 가격으로 판다고 생각하면 된다.
'문제풀이 > Greedy' 카테고리의 다른 글
[Python/파이썬] 백준 17451번 평행 우주 (0) | 2024.05.03 |
---|---|
[Python/파이썬] 백준 19598번 최소 회의실 개수 (0) | 2024.05.02 |
[Python/파이썬] 백준 4796번 캠핑 (0) | 2024.02.28 |
[Python/파이썬] 백준 2847번 게임을 만든 동준이 (0) | 2024.01.25 |
[Python/파이썬] 백준 16435번 스네이크버드 (0) | 2024.01.24 |