AtCoder Regular Contest 002

C - コマンド入力


Time limit時間制限 : 2sec / Memory limitメモリ制限 : 64MB

問題文

高橋君は友達と格闘ゲームで対戦をすることにしました。
格闘ゲームは A, B, X, Y4 種類のボタンを連続で入力するコマンドにより技を繰り出し戦うゲームです。
しかし、普段格闘ゲームで遊ばない高橋君にとってコマンドの入力は難しく、友達に勝てそうにありません。
そこで余っている LR のボタンに連続した 2 つのボタン入力をショートカットとして割り当てることで、コマンドの入力を短縮したいと思います。
例えば、コマンドが ABXY だと 4 回ボタンを入力する必要がありますが、LABRXY を割り当てることで LR2 回のボタン入力に短縮できます。
LR を用いて入力をなるべく短くした時に必要なボタンの入力回数を求めなさい。

入力

入力は以下の形式で標準入力から与えられる。
N
c_{1}c_{2}...c_{N}
  • 1 行目にコマンドに必要なボタンの入力回数を表す N(1 ≦ N ≦ 1000)が与えられる。
  • 2 行目にコマンドの内容を表す N 文字の文字列が与えられる。
  • i 文字目の文字である c_{i} は、A, B, X, Y のいずれかで与えられる。

出力

ショートカットを用いてコマンド入力に必要なボタンの入力回数を最小化したときの、ボタン入力回数を標準出力に 1 行で出力せよ。
なお、最後には改行を出力せよ。

入力例 1

4
ABXY

出力例 1

2
  • LABRXY を割り当てることで入力を LR に短縮することができ、ボタンの入力回数は 2 回となります。

入力例 2

13
ABABABABXBXBX

出力例 2

7
  • LABRBX を割り当てることで入力を LLLARRR に短縮することができ、ボタンの入力回数は 7 回となります。

入力例 3

8
AABBAABB

出力例 3

4
  • LAARBB を割り当てることで入力を LRLR に短縮することができ、ボタンの入力回数は 4 回となります。

Source name

ARC 002

Submit提出する