C - コマンド入力

Contest Duration: 2012-05-02(Wed) 12:00 - 2012-05-02(Wed) 13:30 (local time) (90 minutes) Back to Home

C - コマンド入力 Editorial

Time Limit: 2 sec / Memory Limit: 64 MB

問題文

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

入力

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

 $N$ 
 $c_{1}c_{2}...c_{N}$

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

出力

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

入力例 1

Copy

4
ABXY

4
ABXY

出力例 1

Copy

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

入力例 2

Copy

13
ABABABABXBXBX

13
ABABABABXBXBX

出力例 2

Copy

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

入力例 3

Copy

8
AABBAABB

8
AABBAABB

出力例 3

Copy

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

Source Name

ARC 002