[백준/c++] BOJ 1439 - 뒤집기

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

1439번: 뒤집기

 

문제 설명

0과 1로만 이루어진 문자열 S를 입력받는다. 문자열을 뒤집으면 0은 1로, 1은 0으로 바뀐다. 연속된 숫자를 잡고 뒤집어 문자열의 모든 숫자를 같게 만들어야 한다. 입력된 문자열의 모든 숫자를 같게 하기 위해 뒤집는 최소 횟수를 구하라.

S의 길이는 100보다 작다.

 

해결

입력받는 문자열의 모든 숫자를 0 또는 1로 통일시켜야 한다. 뒤집을 때는 연속된 숫자의 집단을 한번에 뒤집는다.

따라서 연속된 집단이 더 적은 숫자 (0 또는 1) 집단의 개수만큼 뒤집으면 되는 것이다.

0이 연속되는 집합과 1이 연속되는 집합의 개수를 각각 구해 최솟값을 출력하면 된다.

 

코드

#include <bits/stdc++.h>
using namespace std;

	char str[1000001];
int main() {
	char ck = '1', * p = str;
	int one = 0, zero = 0;
	cin >> str;

	while (*p) {
		if (str == p) {
			ck = *p; p++; continue;
		}
		if (ck == *p) {
			p++;
			continue;
		}
		if (*p == '0') {
			one++;
			p++; ck = '0';
		}
		else {
			zero++; p++; ck = '1';
		}
	}
	--p;
	if (*p == '1') one++;
	else zero++;

	if (one < zero) cout << one;
	else cout << zero;
}