[그리디/백준] 11051번 : 주식

-문제 : https://www.acmicpc.net/problem/11501

 

스스로 푼 문제다! Silver Level 2 문제. 

처음에는 증가하는 부분수열 문제인가? 싶었는데, 1 1 3 1 2 같은 경우 부분 수열이 [1,1,3], [1,2] 두개가 있어서 이거를 어떻게 해야할지 몰랐다. 그래서 생각한게 완전탐색. 이걸로 돌리면 예제는 다 맞는데, 시간 복잡도가 n^2이라서 시간 초과가 떴다. 

 

이전에 그리디에서 완전탐색으로 쓴맛을 많이 봤기에 어떻게 해야하나 생각을 했다. 

순간 떠오른 방법이 리스트 거꾸로 진행하는 것. 그러면서 작은 인덱스의 값이 더 크다면 result라는 리스트의 해당 인덱스 값을 변경하고, 아니면 누적하는 방법을 생각했다. 

 

그런데 위 방법으로는 8%에서 틀리길래 반례를 생각해 봤더니, 1,1,3,1,2,5 였다. 가장 큰 값이 오른쪽 끝에 있을 때 위 방법으로는 

result=[3,3,3,5,5,5]인데 이것보다 [5,5,5,5,5,5]이 더 큰 값을 가진다. 

따라서 data인덱스 값 뿐 아니라 result 인덱스의 값도 같이 비교해준 뒤 result 값을 갱신하는 방식으로 진행했더니 정답이 떴다

 

-정답 풀이:

import sys
input=sys.stdin.readline
for _ in range(int(input())):
    n=int(input())
    data=list(map(int,input().split()))
    result=[0]*n
    result[-1]=data[-1]
    for i in range(n-2,-1,-1):
        if data[i]>data[i+1] and data[i]>result[i+1]:
            result[i]=data[i]
        else:
            result[i]=result[i+1]
    answer=0
    for i in range(n):
        answer+=result[i]-data[i]
    print(answer)