\(S\) を表示させるにあたって、 原則 \(1\) 数字 \(1\) ボタン入力が必要です。例外は 00 のボタンがある 0 のみです。

0 が複数連続している部分、具体的には 0 が \(z\) 個連続している部分については、ボタンを \(\lceil z/2 \rceil\) 回押すことで入力できます ( \(\lceil x \rceil\) は \(x\) の小数点以下切り上げ )

解法1. 先頭から貪欲に押す

以下の通りボタンを入力すると、押す回数が最小になります。

• 未入力の部分の先頭に 0 が \(2\) つ連続していれば、それらをまとめて入力する。
• そうでないとき、先頭の数字を \(1\) つ入力する。

これは、ループ等を活用するとシミュレートできます。

実装例 (C++):

#include<bits/stdc++.h>

using namespace std;

int main(){
  string s;
  cin >> s;
  int l=s.size();
  int p=0,res=0;
  while(p<l){
    res++;
    if((p+1)<l && s[p]=='0' && s[p+1]=='0'){p+=2;}
    else{p++;}
  }
  cout << res << "\n";
  return 0;
}

解法2. 0 の連続を検出する

0 が連結する部分を(全て)検出し、そのような部分についていくつ 0 が続くか計上すればそこから答えが求められます。

実装例 (C++):

#include<bits/stdc++.h>

using namespace std;

int main(){
  string s;
  cin >> s;
  int l=s.size();
  int z=0,res=0;
  for(auto &nx : s){
    if(nx=='0'){
      z++;
    }
    else{
      res+=(z+1)/2;
      z=0;
      res++;
    }
  }
  res+=(z+1)/2;
  cout << res << "\n";
  return 0;
}