[BOJ] 20365 블로그2 - C++

https://www.acmicpc.net/problem/20365

20365번: 블로그2

 

아이디어

번갈아가며 나오는 색을 가장 적은 횟수로 칠해야 한다. 색을 다시 덧칠할 수 있음을 이용하면 된다. 연속해서 같은 색을 칠하는 부분을 하나로 생각하고 총 $m$개의 구역으로 나눌 수 있다고 하자. 빨간색과 파란색은 $\frac{m}{2}$내지 $\frac{m}{2} + 1$개의 구역을 가질 것이다. 첫 시도에 둘 중 많은 색을 칠하고 $\frac{m}{2}$번의 색을 칠하는 경우가 최소가 된다.

 

코드

#include <iostream>
#include <string>

using namespace std;

int main() {
    cin.tie(nullptr);
    cout.tie(nullptr);
    ios_base::sync_with_stdio(false);

    int n;
    cin >> n;
    string s;
    cin >> s;

    int cnt = 1;
    char prev = s[0];
    for (int i = 1; i < n; i++) {
        if (prev != s[i]) {
            cnt++;
            prev = s[i];
        }
    }

    cout << cnt / 2 + 1;
}