[실버 4] 백준 25214 - 크림 파스타 (파이썬)

분류 : 다이나믹 프로그래밍

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

풀이

각 인덱스 i에 대해, D[i]는 A[0]부터 A[i]까지의 최솟값, E[i]는 E[i-1]과 (A[i] - D[i]) 중 더 큰 값이다.

즉, E[i]는 앞에서부터 지금까지의 최댓값을 유지하면서, A[i]에서 이전까지의 최솟값을 뺀 값 중 최대를 갱신한다.

D = [0] * N
E = [0] * N

D[i]는 A[0] ~ A[i] 중 최솟값을 나타내고, E[i]는 지금까지의 A[i] - D[i] 중 최대를 나타낸다.

D[0] = A[0]
for i in range(1, N) :
    D[i] = min(D[i - 1], A[i])

최솟값 갱신은 위와 같이 작성하며, D[i]는 A[0] ~ A[i]에서의 최솟값을 저장한다.

E[0] = 0
for i in range(1, N) :
    E[i] = max(E[i - 1], A[i] - D[i])

E[i]는 이전 최댓값과 현재 A[i] - D[i] 값 중 큰 것을 유지한다.

코드

# 백준 25214 - 크림 파스타
# 분류 : 다이나믹 프로그래밍

N = int(input())
A = list(map(int, input().split()))

D = [0] * N
E = [0] * N

D[0] = A[0]
for i in range(1, N) :
    D[i] = min(D[i - 1], A[i])

E[0] = 0
for i in range(1, N) :
    E[i] = max(E[i - 1], A[i] - D[i])

print(*E)