백준 1439번: 뒤집기

[문제 링크]

1439번: 뒤집기

---

간단한 그리디 알고리즘 문제였다.

 

먼저 입력으로 주어지는 문자열에서 같은 숫자로 이루어진 묶음을 하나의 문자로 압축시켰다.

ex) 000/11/00 -> 0 1 0

 

이렇게 압축한 다음 보았을 때 0과 1중 그 개수가 더 적은 숫자를 뒤집는 것이 곧 최소한의 횟수가 된다는 것을 알 수 있다.

---

#include <iostream>
#include <string>
using namespace std;

int cnt[2];

int main(void)
{
	string S;
	cin >> S;

	char idx = '2';

	for (int i = 0; i < S.length(); i++)
		if (idx != S[i])
		{
			idx = S[i];
			cnt[S[i] - '0']++;
		}

	int ret = cnt[0] < cnt[1] ? cnt[0] : cnt[1];

	cout << ret << endl;

	return 0;
}

알고리즘 200일 프로젝트 - 129 day