홍준이는 요즘 주식에 빠져있다. 그는 미래를 내다보는 눈이 뛰어나, 날 별로 주가를 예상하고 언제나 그게 맞아떨어진다. 최대 이익이 얼마나 되는지 계산하시오.
3가지 행동을 if문으로 나눴다. 다음 주가가 떨어지는데 주식이 없으면 아무것도 안한다. 주식이 최고가면 판다. 최고가가 아니면 무조건 산다. 최고가 이후에 팔 기회가 생기면 판다. 논리상 별 문제 없어보이는데 틀렸다. 반례가 있는 것 같은데 특별히 찾지 못했다. 다른 방법은 없을까? if문이 좀 지저분하기도 해서 다시 생각해보았다.
import sys
input = sys.stdin.readline
T = int(input())
for _ in range(T):
N = int(input())
stock = list(map(int, input().split()))
benefit = 0
count = 0
price = 0
maxPrice = max(stock)
maxPriceIndex = stock.index(maxPrice)
for i in range(len(stock)-1):
if stock[i] > stock[i+1] and count == 0: # 아무 것도 안한다
continue
elif stock[i] == maxPrice: # 최고가에 판다
benefit += count * (stock[i] - price/count)
count, price = 0, 0
elif stock[i] > stock[i+1] and i > maxPriceIndex:
benefit += count * (stock[i] - price/count)
count, price = 0, 0
else: # 최고점 아니면 풀매수
count += 1
price += stock[i]
if count:
benefit += count * (stock[-1] - price/count)
print(int(benefit))
이 방법은 최댓값도 계산해놓지 않는다. 뒤에서부터 오면서 최댓값을 찾아간다. 꼭 최댓값이 아니더라도 다음값보다 크다면 차익실현한다. 주가가 오른 경우와 같다. 최댓값과 현재주가를 뺀 값을 쭉 더해주면 최댓값에서 매수한 모든 주식을 판 것과 같은 결과를 만든다.
반복문을 뒤집은 것만으로 코드가 간단해질 수 있다는 게 신기하다. 역시 아이디어 싸움!!!! 순서가 중요한 경우 정렬을 안쓰는데 뒤에서부터 반복문 도는 방법도 떠올리자!
import sys
input = sys.stdin.readline
T = int(input())
for _ in range(T):
N = int(input())
stock = list(map(int, input().split()))
benefit = 0
maxPrice = 0
for i in range(len(stock)-1, -1, -1):
if stock[i] > maxPrice:
maxPrice = stock[i]
else:
benefit += maxPrice-stock[i]
print(int(benefit))