[BOJ/백준 1439][C++] 뒤집기

문제

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

백준 1439

 

문제 내용

입력으로 주어진 문자열의 숫자를 전부 같게 만들기 위해 몇 번을 뒤집어야 하는지를 구하면 된다.

110001의 경우 가운데에 있는 000을 111로 한 번만 바꾸면 111111이 되기 때문에 답은 1이다.
1111111의 경우 뒤집지 않아도 숫자가 전부 같으므로 답은 0이 된다.

 

문제 풀이

처음에는 1로 이루어진 문자열의 개수와, 0으로 이루어진 문자열의 개수를 구한 다음 더 작은 것의 개수를 출력하는 풀이를 떠올렸다.

ex) 1100010011111
1로 이뤄진 문자열 : 11, 1, 11111 => 3개
0으로 이뤄진 문자열: 000, 00 => 2개
따라서 답은 2개

하지만 위의 방법을 구현하다보니 인덱스 처리나 경우를 제대로 고려하기가 까다로워서 다른 방법을 시도했다.

 

 

먼저 연속된 문자열을 하나의 블록이라고 생각해 보자.

아래와 같이 블록의 개수가 짝수인 경우 또는 홀수인 경우로 나눌 수 있을 것이다.

1. A B A B  또는  B A B A
2. A B A B A  또는  B A B A B

우리는 위에서 블록의 개수가 더 작은 쪽을 출력하면 된다.

1번의 경우는 A와 B 모두 2개니까 2를 출력하고, 2번의 경우는 A는 3개 B는 2개니까 2를 출력하게 될 것이다.

 

이를 쉽게 구하려면 str[i] != str[i-1] 인 경우를 세고, 아래 그림처럼 계산하면 된다.

홀수인 경우 (바뀌는 횟수+1)/2, 짝수인 경우 (바뀌는 횟수)/2를 해주면 풀린다.

물론 코드에서는 홀수 짝수 구분 없이 +1 한 후에 2로 나누어주면 된다. (어차피 소수점 계산할 거 아니니까..)

 

코드

#include <iostream>

using namespace std;

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

    int cnt = 0; // 0 -> 1 또는 1 -> 0 으로 바뀌는 횟수
    for (int i = 1; i < str.size(); i++) {
        if (str[i] != str[i - 1]) {
            cnt++;
        }
    }
    cout << (cnt + 1) / 2;
}