問題一覧 > 通常問題

No.1924 3 color painting on a line

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 11
作問者 : 37zigen37zigen / テスター : tassei903tassei903
3 ProblemId : 3373 / 自分の提出
問題文最終更新日: 2022-04-30 02:31:26

問題文

$N$ 個の真っ白なマスが一列に並んでいました。YUKI は赤、緑、青の3色のペンキで各マスを塗り分けようと思っています。

$N$ 文字の文字列 $S$ は YUKI の思い描いていた塗分けを表しており、 $i$ ($1 \leq i \leq N$) 番目の文字 $S[i]$ がRならば赤、Gならば緑、Bならば青で、 先頭から $i$ 番目のマスを塗りたいです。

次の操作を、$S$ が表す塗分けになるまで繰り返します。
  • $1 \leq L \leq R \leq N$ を満たす整数 $L, R$ を選び、先頭から $L, L+1, \ldots, R$ 番目のマスを単色の好きな色で塗りつぶす。 すでに塗られていた場合は、上書きされる。
$S$ が表す塗分けになるための最小の操作回数を求めてください。

入力

$N$
$S$

一行目に整数 $N$、2行目に文字列 $S$ が与えられます。

  • $1 \leq N \leq 10^5$
  • $S$ は RGBからなる文字列

出力

$S$ が表す塗分けになるための最小の操作回数を出力してください。

サンプル

サンプル1
入力
1
R
出力
1

サンプル2
入力
3
RGR
出力
2

サンプル3
入力
3
RGB
出力
3

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。