[백준 1439번] 뒤집기

문제 링크: https://www.acmicpc.net/problem/1439 

1439번: 뒤집기

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

 

연속된 숫자를 한 번에 뒤집을 수 있기 때문에, 먼저 연속된 숫자들을 하나로 합쳐줍니다.

그리고 남은 숫자들 중에서 개수가 더 적은 숫자를 하나씩 뒤집어주면 됩니다.

 

0001100

-> 010

-> 000 (1번)

 

<C++소스코드>

#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
 
int main() {
    ios_base::sync_with_stdio(false);
    string s; cin >> s;
    char c = s[0];
    for (int i = 1; i < s.length(); i++) {
        if (c == s[i])s[i] = '.';
        else {
            c = s[i];
        }
    }
    int zero = count(s.begin(), s.end(), '0');
    int one = count(s.begin(), s.end(), '1');
    cout << min(zero, one);
    return 0;
}