読者です 読者をやめる 読者になる 読者になる

SRM 521 Div2 Easy RedAndGreen

問題

赤と緑のタイルが一列に並んでいる.このタイルの色を書き換えて赤のタイルは必ず緑のタイルよりも左に来るようにしたい.最小の塗り替え回数を答えよ.

解答

どの地点を境目にするか決め,それより左で緑のタイル,右で赤のタイルの数を数える.この最小の値を返す.

class RedAndGreen
{
public:
  int minPaints(string row)
    {
      int n = row.size();
      int res = n;
      for(int i = 0; i <= n; i++){
        int c = 0;
        for(int j = 0; j < n; j++){
          if (j < i && row[j] != 'R') c++;
          if (j > i && row[j] != 'G') c++;
        }
        res = min(res, c);
      }
      return res;
    }
};