17615号

質問する

赤いボールと青いボールが『図1』に示すように一直線に混ざっていると、同じ色のボールが隣接して置かれるようにボールを動かしたい.ボールを動かすルールは以下の通りです.

の隣に違う色のボールがあれば、そのボールを全部スキップすることができます.つまり、赤いボールは隣の青いボールを一度に飛び越えることができます.同様に、青いボールは隣の赤いボールの山を一度に飛び越えることができます.

で移動できるボールは1色しかありません.つまり、赤いボールを先に移動した場合、次は赤いボールしか移動できません.同様に、最初に青いボールを移動した場合、次回も青いボールしか移動できません.

例えば、最初に頬が『図1』で見たように、赤い頬を『図2』で見たように移動し、『図3』で見たように移動すれば、2回で同じ色の間に集まることができる.

逆に、青いボールを選択して、で見たように移動(矢印の数字は移動の順序を表す)すると、同じ色のボールの間に集まるには4回移動する必要があります.

直線上のボールについての情報が与えられたら、ルールに従ってボールを移動し、同じ色の間に集まり、最小の移動回数を検索するプログラムを作成します.

入力

1列目はボールの総数Nを与える.(1≦N≦500000)次の行にはスペースがなく、球の色を表す文字R(赤い球)またはB(青い球)である.文字列は、RまたはBのいずれかのみを与えることができ、この場合、答えは0である.

しゅつりょく

最小移動回数を出力します.

N = int(input())
S = input()

# 빨간색 count 저장
red = S.count('R')
# 파란색 count 저장
blue = N - red
# 빨강, 파랑 중 더 개수가 적은 것 저장
ans = min(red, blue)
cnt = 0

#반복문 돌면서, 연속적인 것 count
for i in range(N):
    if S[i] != S[0]:
        break
    cnt += 1

# 만약에 연속 count한게 빨간색이었다면, 위의 답 vs <전체 빨강 개수 - 앞에서부터 연속 빨강 개수> 중 적은 것 저장
if S[0] == 'R':
    ans = min(ans, red - cnt)
# 만약에 연속 count한게 빨간색이었다면, 위의 답- <전체 파랑 개수 - 앞에서부터 연속 파랑 개수> 중 적은 것 저장
else:
    ans = min(ans, blue - cnt)

cnt = 0
# 반복문 거꾸로 돌면서 끝에서 얼마나 연속되는지 저장
for i in range(N-1, -1, -1):
    if S[i] != S[N - 1]:
        break
    cnt += 1
#만약 연속 count했던게 빨강이었다면, 위의 값 vs <전체 빨강 개수 - 뒤에서부터 연속 빨강 개수> 
if S[N - 1] == 'R':
    ans = min(ans, red - cnt)
#만약 연속 count했던게 파랑이었다면, 위의 값 vs <전체 파랑 개수 - 뒤에서부터 연속 파랑 개수>
else:
    ans = min(ans, blue - cnt)
print(ans)

# 최소값을 구하기 위해서 계속해서 mid으로 답을 갱신해나간다.

優先度

<最小>->赤と青の数

<両者のうち最小>->1回vs「全赤/青-前から数えたときに連続する赤/青」

<両者のうち最小>>2回vs「全赤/青-後から数えるとき連続する赤/青」

赤/青の合計数から、前後の連続する赤/青の数を減算する理由:

の末尾から連続すると、そのボールの山は移動する必要がなく、分かれたものだけが山の方向に移動すればいいのです.これは回数

を意味します.