백준 1439 - 뒤집기

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

힌트

1로 만들기 vs 0으로 만들기 둘 중 최소가 되는 횟수가 최적해이다.

---

풀이

모든 수를 1로 만들거나 0으로 만들어야 한다.

 

어떻게 하면 최소가 될 수 있는지 알 수 있을까?

 

문제에서 이야기한 전체를 뒤집는 것은 사실 의미 없는 행동이다.

 

문자열에서 0의 묶음 개수를 x, 1의 묶음 개수를 y라고 할 때 전체를 뒤집으면 x랑 y의 값이 서로 뒤바뀔 뿐이기 때문이다.

 

그러면 우리는 각 묶음의 개수 중 최소가 바로 정답이 됨을 깨달을 수 있다.

 

구현의 편의를 위해 erase를 사용하여 중복 문자열을 없애버린 뒤 0과 1이 나타나는 횟수를 각각 세서 그중 최소를 출력하면 된다.

 

전체 코드

#include <bits/stdc++.h>

using namespace std;

string s;
int one, zero;

int main()
{
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cin >> s;
  s.erase(unique(s.begin(), s.end()), s.end());

  for (int i = 0; i < s.size(); ++i)
  {
    if (s[i] == '0')
      ++zero;
    else
      ++one;
  }

  cout << min(zero, one);
}

제출 기록