누적합 응용 - prefix/suffix min/max 배열 이용한 테크닉

1. 문제

 

29726번: 숏코딩의 왕 브실이 (acmicpc.net)

29726번: 숏코딩의 왕 브실이

 

2. 풀이

 

$$\sum_{i = 1}^{L-1} A_{i+1} - A_{i} = A_{L} - A_{1}$$을 관찰하는 것은 어렵지 않다.

 

주어진 합은 배열을 알면 양쪽 끝의 두 원소만을 이용해서 구할 수 있다.

 

이 의미는, $A_{1}, A_{2}, A_{3}, ... , A_{N}$이 주어질때, 중간의 원소 $A_{2}, A_{3}, ... ,A_{N-1}$는 지우더라도,

 

합이 변하지 않는다는 뜻이다.

 

그래서 왼쪽이나 오른쪽에서부터 차례대로 최대 M개를 지워서 양쪽 끝의 차이로 최댓값을 구하면 되는데

 

어떻게 지워야 최대가 될지.. 그게 어렵다

 

먼저 생각해야할 것은 주어진 합이 $A_{L} - A_{1}$이므로 $A_{L}$이 최대이고 $A_{1}$이 최소여야, 

 

주어진 합이 최대이다.

 

zero index일때, 왼쪽에서부터 i개를 지우면 $A_{i}$이다. 여기서 i = 0,1,2,3,..,M

 

각각의 i에 대하여 오른쪽에서부터 최대 M-i개를 지울 수 있다.

 

0개 지우면 $A_{N-1}$, 1개 지우면 $A_{N-2}$, ... M-i개 지우면 $A_{N-1 - (M-i)}$

 

여기서 핵심은 최대 M개 지우는 것이지 꼭 M개 전부 안지워도 된다는 것이다.

 

 

 

 

그 말은 i = 0 , 1, 2, ..., M에 대하여 구간 $A_{1}, A_{2}, ... , A_{i}$에 있는 가장 작은 값 $A_{k}$를 선택하고

 

반대 구간 $A_{N-1-M+i}, ... , A_{N-1}$에서 가장 큰 값 $A_{j}$를 선택한다면...

 

왼쪽에서는 k (< i)개, 오른쪽에서는 N-1-j (< M-i)개를 지운 형태이고, 

 

두 경우에 지운 개수의 합은 M개보다 작거나 같기 때문에 조건에 맞다.

 

--------------------------------------------------------------------------------------------------------------------------------------

 

그러면 모든 i = 0,1,2,3,...,M에 대해 구간 0~i에서 최솟값, N-1-M+i ~ N-1에서 최댓값을 찾아야한다는 말이다.

 

당연히 각각 구간의 길이만큼 시간이 걸리기 때문에 N,M이 충분히 큰 20만에서 $O(N^{2})$정도의 시간이라 시간초과다.

 

각 구간 내에서 최솟값과 최댓값을 바로 찾을 수 있을까?

 

방법은 미리 구간마다 최솟값, 최댓값을 구해놓는 것이다.

 

왼쪽에서 오른쪽으로 순회해서 누적합을 구하듯이, 최솟값을 미리 구해놓는다.

 

i번에 왔을때는, i-1번까지 구한 최솟값, A[i]번 원소 중 더 작은 값이 0~i 구간 내의 최솟값이다.

 

prefix = [A[0]]

for i in range(1,n):
        
    prefix.append(min(prefix[-1],A[i]))

 

 

이렇게 전처리 해놓으면 0~i 구간에서 최솟값은 prefix[i]로 O(1)에 구할 수 있다.

 

마찬가지로 오른쪽에서 왼쪽으로 순회해서 누적합을 구하듯이, 최댓값을 미리 구해놓는다.

 

suffix = [0]*n

suffix[-1] = A[-1]

for i in range(n-2,-1,-1):
    
    suffix[i] = max(suffix[i+1],A[i])

 

 

이렇게 전처리해놓으면 i~n-1 구간에서 최댓값은 suffix[i]로 O(1)에 구할 수 있다.

 

따라서 suffix[N-1-M+i] - prefix[i]가 주어진 배열에서 최대 M개를 지울때 가능한 합의 최댓값이다.

 

이를 모든 i = 0,1,2,..,M에 대해 검사해서 최댓값을 찾으면 O(N)에 문제를 해결할 수 있다

 

여기서 조심할 점은 합이 음수가 나올 수 있기 때문에 초기값을 0이 아니라 -10000000000000000같이 음수로 작은 값을 해줘야한다

 

n,m = map(int,input().split())

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

prefix = [A[0]]

for i in range(1,n):
        
    prefix.append(min(prefix[-1],A[i]))

suffix = [0]*n

suffix[-1] = A[-1]

for i in range(n-2,-1,-1):
    
    suffix[i] = max(suffix[i+1],A[i])
    
answer = -1000000000000000000000000

for i in range(m+1):
    
    if answer < suffix[n-1-m+i] - prefix[i]:
        
        answer = suffix[n-1-m+i] - prefix[i]

print(answer)

 

 

근데 뭐 둘 중 하나만 구해도 충분하다.

 

A[end] - A[start]를 최대화시킬때, A[start]를 i = 0,1,2,3,..,m에 대하여 A[i]라고 고정하면...

 

A[end]에서는 suffix배열로 구한 최댓값 suffix[n-1-m+i]으로 해서 모든 i에 대해 검사해서 구하는 최댓값과 동일하다.

 

그런데 직관적으로나 논리적으로나 위에서 구한 논리가 더 멋있다?고해야하나 

 

n,m = map(int,input().split())

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

suffix = [0]*n

suffix[-1] = A[-1]

for i in range(n-2,-1,-1):
    
    suffix[i] = max(suffix[i+1],A[i])
    
answer = -1000000000000000000000000

for i in range(m+1):
    
    if answer < suffix[n-1-m+i] - A[i]:
        
        answer = suffix[n-1-m+i] - A[i]

print(answer)