[백준 1439] 뒤집기 (C#, C++) - soo:bak

문제 링크

1439번 - 뒤집기

설명

0과 1로 이루어진 문자열을 연속 구간 단위로 뒤집어서 모든 문자를 같게 만들 때, 필요한 최소 횟수를 구하는 문제입니다.

접근법

연속된 같은 문자를 하나의 그룹으로 봅니다.

문자열을 순회하면서 0 그룹의 개수와 1 그룹의 개수를 각각 셉니다.

모든 문자를 같게 만들려면 0 그룹을 모두 뒤집거나 1 그룹을 모두 뒤집어야 하므로, 두 개수 중 작은 값이 정답입니다.

---

Code

C#

using System;

class Program {
  static void Main() {
    var s = Console.ReadLine()!;
    var cnt0 = 0;
    var cnt1 = 0;
    var prev = s[0];
    if (prev == '0') cnt0++; else cnt1++;

    for (var i = 1; i < s.Length; i++) {
      if (s[i] == prev) continue;
      prev = s[i];
      if (prev == '0') cnt0++; else cnt1++;
    }

    Console.WriteLine(Math.Min(cnt0, cnt1));
  }
}

C++

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

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  string s; cin >> s;
  int cnt0 = 0, cnt1 = 0;
  char prev = s[0];
  if (prev == '0') ++cnt0; else ++cnt1;

  for (size_t i = 1; i < s.size(); i++) {
    if (s[i] == prev) continue;
    prev = s[i];
    if (prev == '0') ++cnt0; else ++cnt1;
  }

  cout << min(cnt0, cnt1) << "\n";

  return 0;
}