문제
홍준이는 요즘 주식에 빠져있다. 그는 미래를 내다보는 눈이 뛰어나, 날 별로 주가를 예상하고 언제나 그게 맞아떨어진다. 매일 그는 아래 세 가지 중 한 행동을 한다.
1.주식 하나를 산다.
2.원하는 만큼 가지고 있는 주식을 판다.
3.아무것도 안한다.
홍준이는 미래를 예상하는 뛰어난 안목을 가졌지만, 어떻게 해야 자신이 최대 이익을 얻을 수 있는지 모른다. 따라서 당신에게 날 별로 주식의 가격을 알려주었을 때, 최대 이익이 얼마나 되는지 계산을 해달라고 부탁했다.
예를 들어 날 수가 3일이고 날 별로 주가가 10, 7, 6일 때, 주가가 계속 감소하므로 최대 이익은 0이 된다. 그러나 만약 날 별로 주가가 3, 5, 9일 때는 처음 두 날에 주식을 하나씩 사고, 마지막날 다 팔아 버리면 이익이 10이 된다.
풀이
T = int(input())
for _ in range(T):
N = int(input())
stock = list(map(int, input().split()))
stock.reverse()
max = stock[0]
sum = 0
for i in range(1, N):
if max < stock[i]:
max = stock[i]
continue
sum += max - stock[i]
print(sum) 이 문제를 푸는 핵심은 전날 대비 "주가가 오를 때"는 주식 하나를 사는 것이고,
전날 대비 "주가가 내릴 때"는 주식을 파는 것이다.
예제의 테스트 케이스 중에서 날 별로 주가가 1, 1, 3, 1, 2 일 때를 보면,
처음 두 날보다 셋째 날의 "주가가 오르기 때문에" 처음 두 날은 주식을 산다.
반면, 셋째 날에 비해 넷째 날에 "주가가 내리기 때문에" 앞서 샀던 주식들을 판다.
마찬가지로 넷째 날에 비해 다섯째 날에 "주가가 오르기 때문에" 넷째날 주식을 사고,
마지막 날은 주식을 다 팔아버리면 된다.
위는 문제에 대한 이해였고, 그걸 나만의 방식으로 풀어 보았다.
주가를 거꾸로 정렬한 상태로 "주가가 내릴 때" 내린 주가만큼을 이익으로 생각하고 총합에 더해주었다.
주가가 2, 1, 3, 1, 1 이라고 치면,
2에서 1로 내릴 때 1만큼의 이익이 생기고
3에서 1로 내릴 때 2만큼의 이익이 2번 생기는 식으로 생각하니 쉽게 풀었다.
