[BOJ][실5][1439] 뒤집기

문제 링크

문제링크

첫 번째 풀이 : 그리디

알고리즘

연속된 숫자들을 하나로 표현했을 때 010101 따위로 표현할 수 있습니다. 이렇게 변형한 뒤 min(0의 갯수, 1의 갯수)를 구하면 됩니다.

최초의 문자를 back이라고 저장하고 back과 다른 값이 나타나면 back을 갱신하면 됩니다.

정답코드

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using pii = pair<int, int>;

const int MAX = 1010;

int n, m, k;
int arr[MAX];
int main()
{
  //freopen("input.txt", "r", stdin);
  ios_base::sync_with_stdio(0); cin.tie(0);
  string s;
  cin >> s;
  char back = s[0];
  int a = 0, b = 0;
  if (back == '0') a++;
  else b++;

  for (int i = 1; i < s.size(); i++) {
    if (back != s[i]) {
      if (s[i] == '0') a++;
      else b++;
      back = s[i];
    }
  }
  cout << min(a, b);
  return 0;
}

Success Notice: 수고하셨습니다.