[백준][C++] 1439: 뒤집기

문제

1439번: 뒤집기

풀이

그리디

 

0과 1의 구역 중에서 더 적은 수의 구역을 뒤집으면 된다. S[i]와 S[i + 1]의 문자가 서로 다르면, 한 구역이 종료된 것으로 S[i]의 구역 수를 1 증가한다. 문자열의 끝까지 검사하여, 개수가 더 적은 구역의 수를 출력한다.

코드

#include <iostream>
#include <algorithm>

using namespace std;


int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);

    string S;
    cin >> S;

    int count_0 = 0;
    int count_1 = 0;

    // 0과 1의 구역 중에서 더 적은 수의 구역을 뒤집는다. 
    // 다음 문자와 다르다면 한 구역 종료
    for (int i = 0; i < S.size(); ++i)
    {
        if (S[i] != S[i + 1])
        {
            if (S[i] == '0')
            {
                count_0++;
            }
            else
            {
                count_1++;
            }
        }
    }

    cout << min(count_0, count_1);

    return 0;
}