327A. Flipping Game

Problem - 327A - Codeforces

---

0과 1로 이루어진 길이 $N$짜리 수열이 있다. 이 수열에서 연속된 구간 $[i,~j]$를 단 한 번만 골라 구간 안에 있는 모든 0을 1로, 1을 0으로 뒤집는다. 뒤집은 후에 1은 최대 몇 개 있을 수 있을까?

 

이 문제는 제한이 매우 작아서 $O(N^{3})$에도 풀 수 있지만, $N$이 커지더라도 풀 수 있는 방법을 생각해 보자.

Maximum Subarray

먼저 Maximum subarray라는 개념을 알아야 한다. Maximum subaray는 배열의 끝 칸에서 끝나는 부분합 중 최댓값을 구하는 알고리즘이다. 식으로 쓰면 $ms[i]$는 $[1,~i]$ 구간에서 $i$를 포함하는 부분합 중 최댓값을 의미한다.

 

배열 $a$에 대해 $ms[i]=\max(ms[i-1]+a[i],~a[i])$이다.

왜요?

$ms[i-1]$까지 계산한 후에 $a[i]$를 추가할 수 있는 경우는 $ms[i-1]$ 뒤에 $a[i]$를 붙이거나 $a[i]$ 단독으로 사용하는 경우뿐이다. $ms[i-1]$ 외의 부분합에 $a[i]$를 붙였을 때 최댓값이 되는 경우는 없다. 그런 경우가 있다면 애초에 $ms[i-1]$을 잘못 계산한 것이다.

---

다시 문제로 돌아오자. 문제에서는 1이 최대 몇 개 존재할 수 있는지 묻고 있다. 일단 원래 배열에서 1의 개수를 센 후, 뒤집었을 때 1의 개수의 변화의 최댓값을 더하면 된다.

 

여기서 다시 부분합을 생각해 보자. 1이 0으로 뒤집히면 해당 구간의 부분합은 1 감소한다. 반대로 0이 1로 뒤집히면 해당 구간의 부분합은 1 증가한다. 따라서 부분합의 변화를 뜻하는 배열 $d$를 다음과 같이 선언할 수 있다.

 

$d[i]=\begin{cases}-1 & (a[i] = 1)\\1 & (a[i]=0)\end{cases}$

 

이제 $d$ 배열에서 부분합의 최댓값을 구하면 뒤집었을 때 1이 몇 개 늘어나는지(또는 줄어드는지) 알 수 있다. $d$에 대해 Maximum subarray를 계산하고, $\max_{i=1}^{n}{ms[i]}$을 구하여 더해주면 된다.

---

어렵..