問題一覧 > 通常問題

No.1924 3 color painting on a line

レベル : / AI推定難易度 : 2325 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 12
作問者 : 37zigen / テスター : tassei903
お気に入りにしたユーザー ProblemId : 3373 / 自分の提出
問題文最終更新日: 2022-04-30 02:31:26
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original

Problem Statement

There were $N$ pure white cells arranged in a row. YUKI wants to paint the cells using paint of 3 colors: red, green, and blue.

A string $S$ of $N$ characters represents the coloring YUKI has in mind. If the $i$-th ($1 \leq i \leq N$) character $S[i]$ is R, she wants to paint the $i$-th cell from the front red; if it is G, green; and if it is B, blue.

The following operation is repeated until the coloring represented by $S$ is obtained.
  • Choose integers $L, R$ satisfying $1 \leq L \leq R \leq N$, and fill the $L, L+1, \ldots, R$-th cells from the front with a single color of your choice. Cells that have already been painted are overwritten.
Find the minimum number of operations needed to obtain the coloring represented by $S$.

Input

$N$
$S$

The integer $N$ is given on the first line, and the string $S$ is given on the 2nd line.

  • $1 \leq N \leq 10^5$
  • $S$ is a string consisting of R, G, and B

Output

Output the minimum number of operations needed to obtain the coloring represented by $S$.

Sample

Sample 1
Input
1
R
Output
1

Sample 2
Input
3
RGR
Output
2

Sample 3
Input
3
RGB
Output
3

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