백준 1439번 C++

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

1439번: 뒤집기

---

문제

다솜이는 0과 1로만 이루어진 문자열 S를 가지고 있다. 다솜이는 이 문자열 S에 있는 모든 숫자를 전부 같게 만들려고 한다. 다솜이가 할 수 있는 행동은 S에서 연속된 하나 이상의 숫자를 잡고 모두 뒤집는 것이다. 뒤집는 것은 1을 0으로, 0을 1로 바꾸는 것을 의미한다.

예를 들어 S=0001100 일 때,

1. 전체를 뒤집으면 1110011이 된다.
2. 4번째 문자부터 5번째 문자까지 뒤집으면 1111111이 되어서 2번 만에 모두 같은 숫자로 만들 수 있다.

하지만, 처음부터 4번째 문자부터 5번째 문자까지 문자를 뒤집으면 한 번에 0000000이 되어서 1번 만에 모두 같은 숫자로 만들 수 있다.

문자열 S가 주어졌을 때, 다솜이가 해야하는 행동의 최소 횟수를 출력하시오.

---

입력

첫째 줄에 문자열 S가 주어진다. S의 길이는 100만보다 작다.

---

출력

첫째 줄에 다솜이가 해야하는 행동의 최소 횟수를 출력한다.

---

예제 입력 1 

0001100

예제 출력 1 복사

1

---

해결방안 ->

0001100일 때 11인부분을 뒤집으면 1은 0으로 바뀌므로 0000000으로 1번만에 문지열의 모든 숫자가 같아진다.

최소로 뒤집을 떄를 구해야 하므로 연속된 0의 구간 , 연속된 1의 구간의 개수를 생각해보자

그리고 bool변수를 하나 두고 0일떄 false , 1일떄 true를 나타내도록 해준다 (변수 이름은 temp로 일단 지어보자)

 

아래의 표는 문자열s가 0~마지막까지 있를떄 temp변수의 값을 나타낸다.

0	0	0	1	1	0	0
false	false	false	true	true	false	false

이렇게 temp값이 변화한다.

 

이때, 연속된 '0' 구간의 개수는 -> 2이다. 그리고 연속된 '1' 구간의 개수는 ->1이다.

즉, temp값이 false->true로 변화할 떄 연속된 '0'의 구간 +1 , temp값이 true ->false로 변화할 떄 연속된 '1'의 구간 +1

이런식으로 계산하면된다.

연속된 '0'의 구간 개수의 변수를 zero, 연속된 '1'의 구간 개수의 변수를 first로 잡아주면

zero == 2, first == 1이 된다.

 

주의해야 할 점은 반복문을 다 돌리고 최종적인 temp에 따라서 변수를 +1증가시켜준다.

zero,first 중 값이 작은 것을 출력시키면 된다.

---

전체 소스 코드->

#include <iostream>

#include <string>

 

int min(int a,int b){ //zero와 first 중 최소 값

    if(a<b){

        return a;

    }

    else{

        return b;

    }

}

using namespace std;

 

int main(void){

    string str;

    cin >> str;

 

    int zero = 0; //연속된 '0'구간의 개수

    int first = 0; //연속된 '1'구간의 개수

    bool is_zero = false;

    for(int i = 0;i<str.size();i++){

       if(i == 0){

           if(str[i] == '0'){

               is_zero = true;

           }

           else if(str[i] == '1'){

               is_zero = false;

           }

       }

        else{

            if(str[i] == '0' && is_zero == false){

                first++;

                is_zero = true;

            }

            else if(str[i] == '1' && is_zero == true){

                zero++;

                is_zero = false;

            }

        }

    }

    if(is_zero == false){

        first++;

    }

    else{

        zero++;

    }

 

   cout << min(zero,first);

 

}