Koala - 11기/코딩테스트 준비 스터디

[ 백준 / Python ] #25214 크림파스타

dudcks 2023. 7. 21. 03:42

문제

 

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

 

25214번: 크림 파스타

각 \(A_i\)가 추가된 직후의 문제의 답 \(N\)개를 공백으로 구분하여 출력한다.

www.acmicpc.net


Algorithm

1 ≤ i ≤ j ≤ len(A)을 만족하는  A[j] - A[i]의 최댓값을 구하는 문제이다.

dp배열을 만들어주고, 각 배열의 첫번째 원소는 i-1까지의 최댓값과 A[i] 와 dp[i-1]까지의 최솟값의 차이중 최댓값을 취한다.각 배열의 두번째 원소는 dp[i-1] 과 A[i]의 최솟값을 취해주고 dp배열을 점점 확장해나가면 된다.

최종 출력은 첫번째원소를 출력해주면 된다.


 

 

Code

input = __import__('sys').stdin.readline

n = int(input())
arr = list(map(int,input().split()))

dp = [[0,1000000000]]

for i in range(1,n+1):
    dp.append([max(dp[i-1][0] , arr[i-1] - dp[i-1][1]),min(dp[i-1][1],arr[i-1])])

for i in range(1,n+1):
    print(dp[i][0], end = ' ')