# AtCoder Regular Contest 002

URL: https://atcoder.jp/contests/arc002/ (opens new window)

# C

n = gets.chomp.to_i
# 添字を合わせるために先頭にABXY以外を追加
c_str = "Z" + gets.chomp
# L, Rのコマンドは16通りなので全部試しても実行時間は大丈夫
l_arr = []
r_arr = []
abxy = ["A", "B", "X", "Y"]
abxy.each do |c1|
  abxy.each do |c2|
    l_arr << c1 + c2
    r_arr << c1 + c2
  end
end

min = 1000
l_arr.each do |l|
  r_arr.each do |r|
    # 同じコマンドだとL, Rどちらか一方しか使わないのと一緒なので(非効率なので)スキップ
    next if l == r
    # i番目までのコマンドを入力するまでの最小コマンド数
    dp = [0]
    prev = c_str[0]
    1.upto(n) do |i|
      # A,B,X,Yのコマンドを入力する場合
      tmp = dp[i-1] + 1
      # 直前のコマンドと合わせてL, Rで入力する場合
      com = prev + c_str[i]
      tmp2 = (com == l || com == r) ? (dp[i-2] + 1) : 1000
      dp[i] = [tmp, tmp2].min
      prev = c_str[i]
    end
    min = dp[-1] if dp[-1] < min
  end
end

puts min
Last Updated: 2020/08/09 18:33