[백준] 11501번: 주식 - python

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

11501번: 주식

 

생각한건 양 옆으로 비교하면서 크면 계속 옆으로 가면서 차이를 비교하는 방식

 

n = int(input())

for i in range(n):
    sum = 0
    m = int(input())
    arr = list(map(int, input().split()))
    
    for j in range(m-1):
        cnt = 0
        idx = j
        while(arr[idx] <= arr[idx + 1]):
            cnt += 1
            idx += 1
            
            if idx >= m-1:          
                break

        sum += arr[j+cnt] - arr[j]
    print(sum)

 

6 4 7 2

에서 3이 나오게 된다.

 

 

다시 짠 코드 출력은 잘 되는데..

 

짜고 보니 O(n^3) ㅋㅋ

n = int(input())

for i in range(n):
    sum = 0
    m = int(input())
    arr = list(map(int, input().split()))
    
    for j in range(m):
        cnt = 0
        max = 0
        for k in range(j, m):
            if arr[j] <= arr[k]:
                if max < arr[k]:
                    max = arr[k]
                    max_idx = k

        sum += arr[max_idx] - arr[j]
    print(sum)

 

 

정정 후 이번엔 뒤에서부터 비교하면서 max설정하면서 빼기

O(n^2) 으로 수정..

 

import sys
input = sys.stdin.readline
n = int(input())

for i in range(n):
    sum = 0
    m = int(input())
    arr = list(map(int, input().split()))

    max = 0
    for j in range(m-1, -1, -1):
        if arr[j] > max:
            max = arr[j]
        
        elif arr[j] < max:
            sum+= (max-arr[j])
    print(sum)

 

 

성공이다.

미래의 일 같은 경우는 뒤에서부터 비교하는 것이 맞는 것 같다.