백준 1439 - 뒤집기(C++)

문제 링크입니다. https://www.acmicpc.net/problem/1439

1439번: 뒤집기

수를 뒤집에 같은 수만으로 만들 때, 최소 횟수를 구하는 문제입니다.

 

어려워보이지만 간단한 문제인데, 전체를 뒤집는다고 하면, 최소 횟수에 + 1을 더하는 행위나 마찬가지입니다.

 

따라서 0의 구역 갯수, 1의 구역 갯수를 구해 더 적은 갯수를 출력하면 됩니다.

 

예를 들어 0001100의 경우

0의 갯수는 2개, 1의 갯수는 1개임으로 1번만 뒤집으면 됩니다.

 

 

자세한 것은 코드를 참고해주세요.

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cstring>
#include <cmath>
#include <map>
#include <vector>

using namespace std;

string x;
vector<pair<int, int>> Re[2];

int main(){
    cin.tie(0);
    cout.tie(0);
    cin >> x;
    char num = x[0];
    int start = 0, fin = 0;
    for(int i = 1; i < x.size(); i++){
        if(num != x[i]){
            fin = i - 1;
            Re[num-'0'].push_back({start, fin});
            start = i;
            num = x[i];
        }
        else fin = i;
    }
    Re[num-'0'].push_back({start, x.size() - 1});
    cout << min(Re[0].size(), Re[1].size());
    return 0;
}

 

 

질문 및 조언은 댓글을 남겨주세요