[BOJ] 1013번. Contact

문제 링크 : https://www.acmicpc.net/problem/1013

문제는 링크 참고.

풀이.

이 문제는 각 문자마다 다음에 뭐가 올 수 있는지를 분석하여서도 풀 수 있다.

하지만 다음과 같이 그래프를 그려 각 문자를 검사하는 상황마다 인덱스를 매겨서 쉽게 풀 수도 있다.

(100+1+ | 01)+

패턴에 맞는 문자열을 위 그래프를 따라가면서 검사해보면 이 그래프가 왜 그려졌는지 쉽게 알 수 있다.

여기서 빨간색 원은 마지막으로 문자열을 검색했을 때 상태가 0번,4번,5번일 경우 맞는 문자열의 상태의 번호를 표시한다.

ex1)

문자열 : 10011001 은 상태가 0→1→2→3→4→5→6→3→4 로 끝나므로, 맞는 문자열이다.

ex2)

문자열 : 101101 은 상태가 0→1→2→8(정의되지 않은 상태) 이므로, 틀린 문자열이다.

위의 그래프를 테이블로 만들어서 str을 검사하면서 돌리면 된다.

#include <stdio.h>
#include <string.h>
 
int main() {
    int T = 0, q = 0;
    int at[8][2] = { {7, 1},
                     {2, 8},
                     {3, 8},
                     {3, 4},
                     {7, 5},
                     {6, 5},
                     {3, 0},
                     {8, 0},
                     {8, 8}
                    };
    char str[205] = "";
    
    scanf("%d", &T);
    
    while (T--) {
        scanf("%s", str);
        
        q = 0;
        
        for (int i = 0 ; i < strlen(str) ; i ++) q = at[q][str[i] - '0'];
        
        if (q == 0 || q == 4 || q == 5)
            printf("YES\n");
        else
            printf("NO\n");
    }
    
    return 0;
}