Codeforces #1499B Binary Removals

문제

https://codeforces.com/contest/1499/problem/B

걸린 시간

- 실패

풀이

C++

#include <bits/stdc++.h>
#define INF 1e9
#define all(c) c.begin(), c.end()
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int tc;
    cin >> tc;
    while(tc--){
        string s;
        cin >> s;
        int i = s.find("11");
        int j = s.rfind("00");
        cout << (i != -1 && j != -1 && i < j ? "NO" : "YES") << "\n";
    }
    return 0;
}

dp 풀이는 아직 찾지 못해서 Tutorial 을 보았는데 정말 쉬운 풀이방법이 있었다.

인접한 숫자는 지우지 못하므로 "11", "00" 두 가지 경우만 따지면 된다. 둘 중 하나만 존재할 경우 "11" 뒤에있는 0을 모두 제거, "00" 앞에있는 1을 모두 제거 가능하므로 무조건 YES 지만, 두개 다 존재할 경우는 적어도 하나씩 남기 때문에 "11" 뒤에 "00" 이 위치하는지 확인하여야 한다.

string 의 find, rfind 메소드를 이용해 "11" 은 앞에서부터, "00" 은 뒤에서부터 어디에 위치하는지를 찾아 비교하면된다.