Div2 250 ColorfulTilesEasy
問題
'R', 'G', 'B', 'Y' で構成される文字列が与えられる.同じ文字が連続しないように一部の文字を変更したい.変更する文字数の最小数はいくつ?
考え方
同じ文字が続いている個所だけ考慮すればよい.というのも,とりあえず変更する文字を決めた場合,変更後の文字に選択肢があるので変更後が隣と同じになることは無い.
同じ文字が続いているところについて考えると,最低限1個おきに変更する必要があるのは自明なので,変更数を最小にするにはその最低限の変更だけすればいい.
で,いくつ変更するかというと,k個続いている場合[k/2]個変更すれば良い.
kが奇数の場合は両端を含まない方を変更するので端数切り捨てです.
コード
#include <vector> #include <string> using namespace std; class ColorfulTilesEasy { public: int theMin(string room) { int change = 0, cont = 1; for( int i = 0 ; i < room.size() - 1 ; ++i ) { if( room[i] == room[i+1] ) { ++cont; } else { change += cont / 2; cont = 1; } } change += cont / 2; return change; } };