[백준] 11501 주식 / 그리디 / python 실2

https://www.acmicpc.net/problem/11501

 

역순으로 풀면 풀리는 문제

 

처음에는 정순으로 푸려고 했다

 

오늘 가격보다 내일 가격 작으면

현재 구매했던 티켓을 다 팔아버리기

 

오늘 가격보다 내일 가격이 크거나 같으면

한장 사기

 

근데 생각해보니

내일 작다고 당장 팔아버리는 것보다

그 다음에 더 큰 값이 나왔을 때 존버하고 파는 게 나은건가?

그런 생각이 들긴 했다

 

처음에 구현했던

<틀린 코드>

t = int(input())
for i in range(t):
    n = int(input())
    a = list(map(int,input().split()))
    #3
    #10 7 6
    #감소수열은 아무것도 안사고, 안파는게 맞음

    #3
    #3 5 9
    #증가 수열은 하루에 하나씩 사고, 마지막날에 전부 파는거

    #5
    #1 1 3 1 2
    #증가 동안 사고, 최고점때 팔고
    #다시 증가 동안 사고...
    purchase=[]
    result=0
    for i in range(n-1):
        if a[i]>a[i+1]:
            for t in purchase:
                result+=(a[i]-t)
            purchase=[]
        else:
            purchase.append(a[i])
    
    for i in purchase:
        result+=a[n-1]-i
    print(result)

 

하지만 이 문제를 역순으로 접근한다면?

나중에 지금보다 더 큰 값이 나오면 어떡하지<<라는 경우를

역순으로 탐색하면 해결할 수 있다

 

역순으로 탐색하며

현재까지 탐색한 원소의 최대값을 max_price로 업데이트해야 한다

-> 현재 원소 값이 max_price보다 크면 max_price값을 업데이트 한다

 

현재 주식 가격이 max_price보다 작다면

주식을 팔아서 max_price-구매가격 만큼 이득을 볼 수 있다

 

t = int(input())
for i in range(t):
    n = int(input())
    a = list(map(int,input().split()))
    #3
    #10 7 6
    #감소수열은 아무것도 안사고, 안파는게 맞음

    #3
    #3 5 9
    #증가 수열은 하루에 하나씩 사고, 마지막날에 전부 파는거

    #5
    #1 1 3 1 2
    #증가 동안 사고, 최고점때 팔고
    #다시 증가 동안 사고...

    # 역순으로 처리?
    
    max_price=0
    result=0

    for i in range(n-1,-1,-1):
        if a[i]>max_price:
            max_price = a[i]
        else:
            result+=max_price-a[i]
    print(result)

 

생각보다 되게 간단한 코드로 해결할 수 있어서 신기했다