1439: 뒤집기

• toc {:toc}

문제 확인하기

풀이

• 아이디어 1 변경될 때마다 flip을 1씩 증가시켜 풀이하자! num[0] 을 타겟값으로 받고 타겟값과 같지 않다면 flip을 증가시키고 타겟값을 비교한 값으로 교환한다.

문제 : 0001100 일 때 0 → 1, 1 → 0으로 갈 때 2번을 모두 세기 때문에 풀이할 수 없다.

• 아이디어 2 그렇다면 0001100 에서 0 → 1일 때는 세지 말고 1 → 0으로 가는 뒷 부분만 flip을 증가시키자!

문제 : 100000 일 때는 flip이 증가하지 않는다.

• 아이디어 3 0과 1 중 개수가 적은 수를 선택해서 해당 뭉치가 탐지된 경우 flip을 증가시킨다.

문제 : 뭉치의 수가 중요한 것이지 0과 1의 개수가 flip 횟수에 영향을 미치지 않는다.

• 아이디어 4 0 뭉치, 1 뭉치를 각각 센다. num[0] 으로 초기값을 설정하고 해당 뭉치에서 다른 뭉치로 넘어갔을 때 해당 뭉치를 카운트한다. 뭉치의 개수를 전부 카운트한 후 둘 중 뭉치수가 작은 수를 반환하면 그 값이 최소 flip 수가 된다.

#include <bits/stdc++.h>
using namespace std;
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
 
    int flip = 0, one=0, zero=0;
    string num;
 
    cin >> num;
 
 
    char target;
 
    if(num.size() == one || num.size() == zero){
        cout << 0 << '\n';
        exit(0);
    }
 
 
    if(num[0] == '0') zero++;
    else one++;
    target = num[0];
 
    for(int i = 1; i < num.size(); i++){
        if(target != num[i]) {
            if(num[i] == '0') zero++;
            else one++;
            target = num[i];
        }
    }
 
    if(zero > one) flip = one;
    else flip = zero;
 
    cout << flip << '\n';
 
    return 0;
}