[Python] 25214번 크림 파스타

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

---

 

26/02/15

 

 

솔브닥 이벤트 때문에 풀게 된 문제 중 하나이다.

---

 

문제 접근 방식:

 

 

최솟값($m$)/최댓값($M$)을 배열의 원소를 하나 하나 보며 갱신해줌으로써 $\mathcal{O}(N)$으로 해결할 수 있다.

$A_{j}-A_{i}$들은 단조증가함은 쉽게 파악할 수 있다.

현재 보고 있는 원소가 최솟값인 경우, 해당 원소를 포함한 수의 차이를 구하는 건 항상 음수로 나오기 때문에 손해이다.

따라서 현재 보고 있는 원소가 최솟값인 경우, 직전 문제의 답과 동일한 답을 추가하면 된다.

현재 보고 있는 원소가 최솟값이 아닌 경우, 현재 보고 있는 원소가 최댓값인지 확인한다.

만약 최댓값이라면 최솟값은 이미 이전에 나왔음이 보장되있으므로, $M-m$을 답으로 추가하면 된다.

만약 최댓값이 아니라면 $A_{i} - m$과 직전 답 중 큰 답을 답으로 추가하면 된다.

---

아래는 내가 위의 접근 방식과 같이 작성한 Python 코드이다. 더보기를 누르면 확인할 수 있다.

# 25214번 크림 파스타
# 그리디 알고리즘
import sys
input = sys.stdin.readline

N = int(input())
ans = [0]
A = list(map(int, input().split()))
m, M = A[0], A[0]
for i in range(1, N):
    if A[i] < m:
        m = A[i]
        ans.append(ans[-1])
    else:
        if A[i] > M:
            M = A[i]
            ans.append(M-m)
        else:
            ans.append(max(A[i]-m, ans[-1]))
print(*ans)