# B. Binary Typewriter [문제 링크](https://codeforces.com/contest/2103/problem/B) ## Problem Statement You are given a binary string $s$ of length $n$ and a typewriter with two buttons: $\mathtt{0}$ and $\mathtt{1}$. Initially, your finger is on the button $\mathtt{0}$. You can do the following two operations: 1. Press the button your finger is currently on. This will type out the character that is on the button. 2. Move your finger to the other button. If your finger is on button $\mathtt{0}$, move it to button $\mathtt{1}$, and vice versa. The *cost* of a binary string is defined as the minimum number of operations needed to type the entire string. Before typing, you may reverse at most one substring (∗) of $s$. More formally, you can choose two indices $1 \le l \le r \le n$, and reverse the substring $s_{l \ldots r}$, resulting in the new string $s_1 s_2 \ldots s_{l-1}\, s_r s_{r-1} \ldots s_l\, s_{r+1} \ldots s_n$. Your task is to find the minimum possible cost among all strings obtainable by performing at most one substring reversal on $s$. ## Input Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows. The first line of each test case contains a single integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the length of the binary string $s$. The second line of each test case contains a binary string $s_1 s_2 \ldots s_n$ ($s_i = \mathtt{0}$ or $s_i = \mathtt{1}$) — the characters of the binary string $s$. It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$. ## Output For each test case, output the minimum cost of string $s$ after performing at most one substring reversal. ## Footnotes (∗) A string $a$ is a substring of a string $b$ if $a$ can be obtained from $b$ by the deletion of several (possibly, zero or all) characters from the beginning and several (possibly, zero or all) characters from the end. ## 풀이 #### 입력으로 들어온 문자열에 대해 cnt를 구하고 문자열에서 "101"이 존재하는 경우 cnt-2, "10"이 존재하는 경우 cnt-1을 출력하면 된다. ``` c++ #include<bits/stdc++.h> using namespace std; int n; string s; int solve() { int cnt = n; if(s[0]=='1') cnt++; // 101꼴 -> -2 // 10꼴 -> -1 bool first1=false, first0=false, last1=false; for(int i=0;i<s.length();i++) { if(i>=1 && s[i]!=s[i-1]) cnt++; if(s[i]=='1' && first1==false) first1=true; else if(s[i]=='0' && first1==true) first0=true; else if(s[i]=='1' && first0==true) last1=true; } if(first1 && first0 && last1) cnt-=2; else if(first1 && first0) cnt--; return cnt; } int main() { ios::sync_with_stdio(0); cin.tie(0); int t; cin >> t; while(t--) { cin >> n >> s; cout << solve() << '\n'; } } ```