[백준 20365번] 블로그2

문제 링크: 

<문제 풀이> 그리디 알고리즘

 

연속된 색은 한 번에 칠할 수 있기 때문에, 이를 하나의 색으로 만들어줍니다.

그다음 가장 많은 개수의 색으로 전체를 먼저 칠한 후 나머지 색으로 하나씩 칠하면 됩니다.

 

BBRBRBBR

-> BRBRBR

-> BBBBBB

-> BRBBBB

-> BRBRBB

-> BRBRBR

 

 

<C++소스코드>

#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
 
int main() {
    ios_base::sync_with_stdio(false);
 
    int n;
    cin >> n;
    string s; cin >> s;
    char prev = s[0];
    for (int i = 1; i < n; i++) {
        if (prev == s[i]) s[i] = ' ';
        else {
            prev = s[i];
        }
    }
    int B = 0, R = 0;
    for (int i = 0; i < n; i++) {
        if (s[i] == 'B')B++;
        else if (s[i] == 'R') R++;
    }
    cout << 1 + min(B, R);
 
    return 0;
}