D - Flip to Gather https://atcoder.jp/contests/abc408/tasks/abc408_d

abc408_d.py

def isdif(c, x):
    return 0 if c == x else 1


T = int(input())
for _ in range(T):
    N = int(input())
    S = list(map(int, input()))
    dp = [[float("inf")] * 3 for _ in range(N + 1)]
    dp[0][0] = dp[0][1] = dp[0][2] = 0
    for i in range(N):
        # 0 -> 0 まだ1の区間に入ってない
        dp[i + 1][0] = min(dp[i + 1][0], dp[i][0] + isdif(S[i], 0))
        # 0 -> 1 1の区間に入った
        dp[i + 1][1] = min(dp[i + 1][1], dp[i][0] + isdif(S[i], 1))
        # 1 -> 1 1の区間のまま
        dp[i + 1][1] = min(dp[i + 1][1], dp[i][1] + isdif(S[i], 1))
        # 1 -> 2 1の区間を抜けた
        dp[i + 1][2] = min(dp[i + 1][2], dp[i][1] + isdif(S[i], 0))
        # 2 -> 2 1の区間を抜けた状態を継続
        dp[i + 1][2] = min(dp[i + 1][2], dp[i][2] + isdif(S[i], 0))
    print(min(dp[N][0], dp[N][1], dp[N][2]))