0이나 1을 뒤집어서 1이 연속인 구간이 최대 1개로 만들기

D - Flip to Gather

D - Flip to Gather

 

 

0과 1로 이루어진 문자열이 주어진다.

 

i번째 문자를 0이면 1로, 1이면 0으로 뒤집는 연산을 0번 이상 한다.

 

이때, 주어진 문자열에서 1이 연속인 구간이 최대 1개가 되도록 만들려고 한다.

 

100111이면, 1이 연속인 구간이 1, 111로 2개이므로 1번째 1을 0으로 뒤집어서 000111로 하면 111인 구간 1개만 존재하여 조건을 만족한다.

 

조건을 만족하게 하는 연산 횟수의 최솟값은?

 

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

 

S1, S2, S3,...,Si에서 0인 것의 개수를 A[i]라고 하자.

 

S1,S2,S3,...,Si에서 1인 것의 개수를 B[i]라고 하자.

 

1이 연속하게 있는 구간이 최대 1개라는 뜻은..

 

어떤 정수 쌍 (L,R)에 대하여 이 구간의 모든 Si가 1로 되게 만들면 된다.

 

이러한 연산의 횟수는?

 

먼저 (L,R) 구간의 모든 0인 것의 개수를 1로 바꿔야하므로, A[R] - A[L-1]개만큼 연산을 수행

 

그리고 (L,R)구간 밖에 1을 0으로 바꿔야하므로, (L,R)구간 밖에 있는 1의 개수는...

 

B[n] - B[R] + B[L-1]개만큼 연산을 수행

 

따라서, 전체 연산 횟수는 B[n] - B[R] +B[L-1] + A[R] - A[L-1]

 

이때, C[i] = A[i] - B[i]이라고 하자.

 

B[n] + A[R] - B[R] - (A[L-1] - B[L-1]) = B[n] + C[R] - C[L-1]

 

그러므로, 모든 정수쌍 1 <= L <= R <= N에 대해, C[R] - C[L-1]의 최솟값을 찾으면 된다.

 

이걸 어떻게 찾지?

 

이때, 정수 R = 1,2,3,...,N에 대하여, 이를 고정하면... C[L-1]의 최댓값을 구하면 C[R] - C[L-1]이 (L,R)에 대해 최솟값이 된다.

 

L <= R이므로, R = 1,2,3,..,N을 가면서 C[i]의 최댓값을 기억하고 있으면 O(N)에 정답을 찾을 수 있다.

 

T = int(input())

for _ in range(T):
    
    n = int(input())

    s = list(map(int,input()))

    A = []

    c = 0
    
    #S1S2,...,Si의 0의 개수 A[i]
    for i in range(n):

        if s[i] == 0:

            c += 1

        A.append(c)    


    B = []

    c = 0
    
    #S1S2,...,Si에서 1의 개수 B[i]
    for i in range(n):
        
        if s[i] == 1:
            
            c += 1
        
        B.append(c)
    
    #어떤 정수 쌍 1 <= L <= R <= N에 대해 (L,R)을 모두 1로 바꾸면 된다.
    #(L,R)의 0의 개수만큼 연산을 수행 A[R] - A[L-1]
    #(L,R) 바깥의 1의 개수만큼 연산을 수행 B[N] - B[R] + B[L-1]
    #B[N] + A[R] - B[R] - (A[L-1] - B[L-1])
    #C[i] = A[i] - B[i]
    C = []
    
    for i in range(n):
        
        C.append(A[i] - B[i])

    v = 10**18
    m = 0
    
    #모든 1 <= L <= R <= N에 대해 C[R] - C[L-1]의 최솟값을 찾는다.
    #R = 1,2,..,N을 고정하고, 그러면 C[L-1]의 최댓값을 알고 있으면, C[R] - C[L-1]이 최소가 된다.
    #R = 1,2,..,N을 순회하면서, 그 이전 구간 (0,R-1)에서 C배열의 최댓값을 기억하고 있는다.
    for r in range(n):
        
        m = max(m,C[r])
        
        if v > B[-1] + (C[r] - m):
            
            v = B[-1] + C[r] - m
    
    print(v)