[BOJ] 1013 Contact

결국 

$$ (100+1+ | -1)+ $$

이 식을 만족하는지 안하는지를 체크하면 된다는 것이다.

 

 처음에 오토마타 전공수업때 배웠던 state machine이 생각났었으나 그렇게 코딩할 생각은 못하고... 조건을 생각해서 전부 노가다로 풀려고 했었다. 그러나 아무리 해도 뭔가 조건이 너무 복잡하고 나오는 경우의 수도 많아서 풀기가 힘들었다.

 

 그래서 가장 처음에 생각했던 state machine을 이용한 풀이를 생각해봤다.

내가 직접그린 NFA다(발그림..)

 

우선 initial state는 S0이며, 위 그림과 같이 상태가 변화한다.

이를 코드로 작성하면,

#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define endl '\n'
using namespace std;
using ll = long long;
using ull = unsigned long long;
using u = unsigned;
using pii = pair<int, int>;

void solve() {
    int state[8][2] = {
        {1, 2},     //s0
        {-1, 0},    //s1
        {3, -1},    //s2
        {4, -1},    //s3
        {4, 5},     //s4
        {1, 6},     //s5
        {7, 6},     //s6
        {4, 0}      //s7
    };
    int current = 0;
    string s;
    cin >> s;

    for(int i = 0; i < s.size(); i++) {
        if(current == -1) break;
        current = state[current][s[i] - '0'];
    }

    if(current == 0 || current == 5 || current == 6) cout << "YES" << endl;
    else cout << "NO" << endl;
}

int main() {
    fastio;
    int T;
    cin >> T;
    for(int i = 0; i < T; i++) {
        solve();
    }
    return 0;
}

 이러한 정말 깔끔한 코드가 나오는데 나는 왜 이걸 조건 하나하나 다 찾아가며 했는지 현타가 오더라...

 

 그리고 이 포스트를 작성하면서 생각난건데 오토마타의 형식언어를 통해 정규식을 만들 수 있는데 이게 그 정규식이 아닌가? 라는 생각이 들었다. 그런 생각이 들고나서 파이썬에는 정규식을 확인할 수 있는 메소드가 있는걸로 아는데 C++에도 있는지 찾아보았다.

 

https://modoocode.com/303

씹어먹는 C++ - <17 - 2. C++ 정규 표현식(<regex>) 라이브러리 소개>

있더라... 현타가 좀 많이 왔다.

 

이를 활용해 코드를 작성해봤다.

#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define endl '\n'
using namespace std;
using ll = long long;
using ull = unsigned long long;
using u = unsigned;
using pii = pair<int, int>;

int main() {
    fastio;
    int T;
    cin >> T;
    regex re("(100+1+|01)+");

    for(int i = 0; i < T; i++) {
        string s;
        cin >> s;
        cout << (regex_match(s, re) ? "YES" : "NO") << endl;
    }

    return 0;
}

 

하... 분명 풀었는데 현타가 정말 많이오는 문제였다.