AT_arc002_3 [ARC002C] コマンド入力

[problemUrl]: https://atcoder.jp/contests/arc002/tasks/arc002_3 高橋君は友達と格闘ゲームで対戦をすることにしました。 格闘ゲームは $ 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 $ 行で出力せよ。 なお、最後には改行を出力せよ。

N/A

N/A