C - 寿司タワー Editorial /

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

寿司とは「シャリ」の上に「ネタ」をのせた食べ物です。

りんごさんは N 個の寿司を積み上げることで寿司タワーを作ろうとしています。N 個の寿司があるということは、N 個のシャリと N 個のネタで、合計 2N 個のパーツがあるということですが、これらのパーツをある順番で積んでいきたいと思っています。

寿司を 1 つ積む方法には以下の 3 通りの方法があります。

  • そのまま積む：シャリ、ネタの順に積まれることになる。
  • ひっくり返して積む：ネタ、シャリの順に積まれることになる。
  • 分解して積む：寿司を分解してシャリとネタを分け、それぞれを別々に積む。

例えば、3 個の寿司を下から順に「ネタ、シャリ、ネタ、ネタ、シャリ、シャリ」と積みたい場合は以下のように積むことができます。

  1. 寿司を 1 つ分解してネタを積む。シャリの方は後で積むために取っておく。
  2. 寿司をそのまま積む。
  3. 寿司をひっくり返して積む。
  4. 取っておいたシャリを積む。

寿司を分解するのは手間がかかるので、りんごさんはできるだけ分解する寿司の個数を少なくしたいと思っています。目的の寿司タワーを作るために分解する寿司の個数の最小値を求めてください。

入力

入力は以下の形式で標準入力から与えられる。

N
S
  • 1 行目には、寿司の個数を表す整数 N (1 ≦ N ≦ 256) が与えられる。
  • 2 行目には、パーツを積む順番を表す長さ 2N の文字列 S が与えられる。S は N 個の 0 と N 個の 1 からなる文字列で、S の i (1≦i≦2N) 文字目が 0 であるときは下から i 番目にシャリを積むことを表し、1 のときは下から i 番目にネタを積むことを表す。

出力

目的の寿司タワーを作るために分解する寿司の個数の最小値を 1 行に出力せよ。出力の末尾に改行を入れること。

入力例1

3
101100

出力例1

1

問題文中の例の通りです。下図は積み方の例を表しており、白い丸はシャリ、赤い長方形はネタを表しています。

figure1

入力例2

5
0000111011

出力例2

3