use proconio::{input, marker::Chars}; fn main() { input! { n: usize, s: Chars, } if n == 1 && s[0] == '0' { println!("1"); return; } // 2桁前まで見る let mut dp = [1_000_000_000_i64; 4]; dp[0b11] = 0; for i in 0 .. n { let mut dp_next = [1_000_000_000_i64; 4]; for prev in 0b00 ..= 0b11 { for c in 0 ..= 1 { let mut cost = dp[prev]; if (s[i], c) == ('0', 1) { cost += 1; } let seq = prev << 1 | c; if seq & 3 == 0b00 { continue; } if seq == 0b010 { continue; } dp_next[seq & 3] = dp_next[seq & 3].min(cost); } } dp = dp_next; } let mut ans = 1_000_000_000_i64; for state in [0b01, 0b10, 0b11] { ans = ans.min(dp[state]); } println!("{ans}"); }