단색 문자열 만들기

$`0`$의 개수와 $`1`$의 개수를 각각 $C_0, C_1$이라고 하자.

만약 $C_0=0$ 또는 $C_1=0$이면 문자열은 처음부터 단색이므로 답은 $0$이다.

만약 $C_0=C_1$이면 문자열 전체를 한 번에 삭제할 수 있으므로 답은 $1$이다.

이제 $C_0 \ne C_1$이고 두 문자가 모두 존재한다고 하자. 더 많이 등장하는 문자를 majority 문자라고 부르자. majority 문자를 $+1$, 나머지 문자를 $-1$로 바꾼 배열을 $A$라고 하자. 전체 합을 $D$라고 하면 $D>0$이다.

삭제할 수 있는 부분 문자열은 정확히 합이 $0$인 구간이다. 따라서 어떤 연산을 여러 번 하더라도 전체 합 $D$는 변하지 않는다. 마지막 문자열은 단색이어야 하므로, 마지막에는 majority 문자만 정확히 $D$개 남아야 한다.

즉, 문제는 다음과 같이 바뀐다.

majority 문자 중 일부를 남기고, 나머지 문자들을 합이 $0$인 연속 구간들로 나누어 삭제한다. 이때 삭제하는 구간의 개수를 최소화한다.

prefix sum을 다음과 같이 정의하자.

$$P_0 = 0,\qquad P_i = A_1 + A_2 + \cdots + A_i$$

구간 $(l+1,\ldots,r)$의 합이 $0$이라는 것은 $P_l=P_r$이라는 뜻이다.

$dp_i$를 앞의 $i$글자까지 처리했고, $i$번째 위치가 현재 경계일 때 필요한 최소 연산 횟수라고 하자. 위치 $j+1$의 문자가 majority 문자라면 이 문자를 남길 수 있다. 이때 이전 경계 $i$에서 $j$까지의 구간을 삭제하려면 $P_i=P_j$여야 한다.

같은 prefix sum을 가진 이전 경계들의 $dp$ 최솟값을 $best$에 저장하면 각 위치마다 $O(1)$에 전이할 수 있다.

전이는 다음 두 경우이다.

• 바로 현재 majority 문자를 남긴다. 비용은 증가하지 않는다.
• 같은 prefix sum을 가진 이전 경계에서 현재 위치 직전까지의 비어 있지 않은 구간을 삭제한 뒤 현재 majority 문자를 남긴다. 비용이 $1$ 증가한다.

모든 위치를 처리한 뒤, 마지막 suffix도 합이 $0$이면 한 번 더 삭제할 수 있다.

전체 시간 복잡도는 $O(N)$, 메모리 복잡도는 $O(N)$이다.