[Codeforces Round 1005(Div. 2)] A. Brogramming Contest

https://codeforces.com/contest/2064/problem/A

Codeforces Round 1005(Div. 2) - A. Brogramming Contest

문제 유형: 그리디, 문자열 처리

시간 제한: 1초

메모리 제한: 256MB

 

문제

One day after waking up, your friend challenged you to a brogramming contest. In a brogramming contest, you are given a binary string∗ s of length n and an initially empty binary string t.

During a brogramming contest, you can make either of the following moves any number of times:

• remove some suffix from s and place it at the end of t, or
• remove some suffix from t and place it at the end of s.

 

To win the brogramming contest, you must make the minimum number of moves required to make s contain only the character 0 and t contain only the character 1. Find the minimum number of moves required.

 

어느 날, 당신의 친구는 당신에게 브로그래밍 대결을 도전했다.

브로그래밍 대결에서는 바이너리 문자열 s와 빈 바이너리 문자열 t를 받는다.

당신은 다음의 연산을 몇 번이고 할 수 있다:

• s의 접미사 부분을 지우고 t의 맨 끝에다가 놓기
• t의 접미사 부분을 지우고 s의 맨 끝에다가 놓기

이기기 위해선, 당신은 최소한의 연산으로 s에는 0만 남기고, t에는 1만 남겨야 한다.

 

입력

The first line contains an integer t (1≤t≤100) — the number of test cases.

The first line of each test case is an integer n (1≤n≤1000) — the length of the string s .

The second line of each test case contains the binary string s.

The sum of n across all test cases does not exceed 1000.

 

첫째 줄에 테스트 케이스의 수 t가 주어진다.

각 테스트 케이스의 첫째 줄에는 n이 주어진다. - s의 길이이다.

둘째 줄에는 바이너리 문자열 s가 주어진다.

 

출력

For each testcase, output the minimum number of moves required.

 

각 테스트케이스별로 최소 연산 수를 구하시오.

 

풀이

s의 0으로만 구성된 prefix를 제외하고, 나머지 suffix 부분에서, 1로만 되어있는 부분과 0으로만 되어있는 부분들의 개수를 구하면 된다.

모두 떼고 1만 있는 부분을 t에 붙이고, t에서 다시 0으로 시작하는 suffix를 뗐다가 s에 붙이고, s에서 다시 1로 시작하는 suffix를 뗀다고 보면 된다. 이를 계속 반복한다고 생각하면 편하다.

 

 

코드

C++

#include <bits/stdc++.h>

using namespace std;

void solve() {
  int n;
  cin >> n;
  string s;
  cin >> s;
  int i = 0;
  while (i < n && s[i] == '0') {
    i++;
  }

  bool flag = false;
  int ans = 0;

  while (i < n && s[i] == '1') {
    flag = true;
    i++;
  }
  if (flag)
    ans++;

  while (i < n) {
    flag = false;
    while (i < n && s[i] == '0') {
      flag = true;
      i++;
    }
    if (flag)
      ans++;

    flag = false;
    while (i < n && s[i] == '1') {
      flag = true;
      i++;
    }
    if (flag)
      ans++;
  }

  cout << ans << "\n";
}

int main(int argc, char *argv[]) {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int t;
  cin >> t;
  while (t--)
    solve();
  return 0;
}