[백준 1439]뒤집기_C++

그리디 알고리즘 유형

문제

문제, 입출력

입출력 예제

★ 0과1로 구성된 문자열을 모두 같은 것으로 바꾸기 위해 최소한의 뒤집기 횟수를 출력해야함. 이때 연속된 문자열은 한번에 뒤집을 수 있음.

★ 풀이 : 

   1과 0밖에 없으니, 1과 0을 뒤집는 경우를 둘 다 구해 횟수가 더 적은 것을 출력함

   이때, 연속된 문자열 카운트는, 연속된 문자열의 첫번째만 카운트 하는 방식으로 함. (연속 여부는 이전 문자와 비교)

 

c++ 코드

#include<iostream>
#include<string>

using namespace std;

int main() {
	string s;
	cin>>s;

	//0을 바꾸는 경우와 1을 바꾸는 경우 모두 구해서 작은걸로 출력할 예정
	int cntZero = 0;
	int cntOne = 0;
		
	//연속된 숫자인지 어떻게 확인할 거임? => 이전 인덱스의 숫자와 비교 ㄱㄱ
	// 연속된 것의 첫번째만 카운트 해주고, 나머지는 카운트 안하면 됨.
	char prev = s[0];
	if (prev == '0')
		cntZero += 1;
	else
		cntOne += 1;

	for (int i = 1; i < s.length(); i++) {
		//0일 경우
		if (s[i] == '0') {
			if (prev != s[i])
				cntZero += 1;
			
		}

		//1일 경우
		if (s[i] == '1') {
			if (prev != s[i])
				cntOne += 1;
		}
		prev = s[i];
	}

	if (cntZero >= cntOne)
		cout << cntOne;
	else
		cout << cntZero;
	
}