[BOJ 16500] 문자열 판별

문제 출처 : https://www.acmicpc.net/problem/16500

 

풀이 :

 

DP문제입니다.

문자열을 처음부터 끝까지 훑으면서 단어들과 매칭합니다

그리고 단어 목록들로 문자열의 현재 시점까지 완성 시킬 수 있는지 없는지 여부를 word배열에 쌓아가는데, 쌓을 때 현재 검사하고있는 S문자열의 바로 앞 문자까지 완성되있는지 여부를 확인하고 완성되어 있으면 word 배열에 완성 됬다고 쌓아가시면 됩니다.

 

#include<stdio.h>
 
char comp[101];
char carr[101][101];
int n,word[101];
 
int main()
{
    scanf("%s", comp);
    scanf("%d\n", &n);
    for (int i = 0; i < n; i++) scanf("%s", carr[i]);
    int i;
    for (i = 0; comp[i]!='\0'; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (comp[i] == carr[j][0])
            {
                int type = 0,k,k1;
                for (k = i + 1, k1 = 1; carr[j][k1] != '\0'&&comp[k] != '\0'&&!type; k++, k1++)if (comp[k] != carr[j][k1])type = 1;
                if (type)continue;
                if (carr[j][k1] == '\0'&&((i>0&&word[i - 1])||i==0))word[k - 1] = 1;
            }
        }
    }
    printf("%d", word[i-1]);
}