주식은 백트래킹 문제로 풀어야하는 문제였음. 처음에는 그리디인가 브루트 포스인가 고민을 많이 했었는데, 처음에 생각한 코드는 이렇다.
t = int(input())
for _ in range(t):
n = int(input())
juka = list(map(int, input().split()))
buy = 0
sell = 0
ju = 0
for i in range(len(juka)):
if i == len(juka):
sell += ju * juka[i]
ju = 0
break
if juka[i] == max(juka[i:]):
sell += ju * juka[i]
ju = 0
else:
buy += juka[i]
ju += 1
print(sell - buy)
처음에는 앞에서부터 보는 것에 집중했었는데, 지금 상태에서 뒤를 봤을 때 지금 상태가 max면 파는 경우, 아니면 현재 주가로 구매를 한다. 마지막으로 총 매출에 총 수입을 빼는 방식으로 답을 내는 방식이다.
근데 시간 초과 오류가 떴고, 현우형의 의견으로 슬라이드를 잘라서 보기로 해봤다.
t = int(input())
for _ in range(t):
n = int(input())
juka = list(map(int, input().split()))
answer = 0
while True:
buy = 0
sell = 0
ju = 0
max_idx = -1
max_temp = -1
if not juka:
break
for i in range(len(juka)):
if juka[i] > max_temp:
max_idx = i
max_temp = juka[i]
for i in range(max_idx):
buy += juka[i]
sell += max_idx * juka[max_idx]
answer += sell - buy
juka = juka[max_idx+1:]
print(answer)
리스트가 다 없어질 때까지 진행하는 것인데, 리스트에서 가장 max인 값과 인덱스를 찾아서 슬라이싱하고 그 뒤에 있는 값은 또 재귀적으로 돌리는 느낌이다. 이것 또한 시간 초과가 안 날일이 없었고,
결국 백트래킹을 생각해봤다.
t = int(input())
for _ in range(t):
n = int(input())
juka = list(map(int, input().split()))
juka.reverse()
max_price = 0
answer = 0
for price in juka:
if price > max_price:
max_price = price
else:
answer += max_price - price
print(answer)
뒤에서 보면서 가는 것이 한 번만 리스트를 확인하는 것이라 시간초과가 나지 않았다.