백준 11501 주식

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

11501번: 주식

문제 접근법 : 주식하나사서 제일비싼가격에 팔아야 하는문제입니다.

 

만약 주식이

3 2 5 10 7 9 8 10 이와같은형태에 있을때

3,2,5는 10이될때 팔면되고

7,9,8도 10이될때 팔면됩니다

 

그렇다면 어떻게 탐색하면 될까요? 뒤에서 탐색을 하는게 가장좋습니다.

뒤에서 탐색한다면 차라리 입력을 거꾸로 바꿔야겠죠?

그렇다면

10 8 9 7 10 5 2 3

이 된다면 처음 왼쪽이 가장 크다고 가정할때 이것보다 더크거나 같은수가 나오면

지금까지 봤던것들을 가장 왼쪽을 기준으로 다팔면됩니다.

그리고 다시 기준을 크거나 같은수의 기준으로 두고 다시 탐색해서 마지막 오른쪽까지 합니다. 그런데 문제점은

마지막 오른쪽 3에서 끝나서 10을 못팔게됩니다. 그렇기때문에 임시로 마지막에 무한대를 넣어줌으로써 팔지못하는경우가 없도록 만듭니다.

 

소스코드 : 

import sys
input = sys.stdin.readline

test = int(input())
for _ in range(test):
    n = int(input())
    l = list(map(int,input().split()))
    l.reverse()
    t = 10000000000000000
    l.append(t)
    left = 0
    res = 0
    for i in range(len(l)):
        if l[left]<=l[i]:
            for k in range(left,i):
                res+=l[left]-l[k]
            left=i
    print(res)

 

궁금한점 혹은 모르는점 어떤질문이든 댓글은 언제나 환영입니다.