[C++] 백준 - 16500 : 문자열 판별

문제 링크

16500번: 문자열 판별

 

풀이 ) DP

  입력을 받을 때 각 문자열의 길이에 대한 data를 저장한다.

  문자열 S를 앞에서부터 순회하면서 부분 문자열로 A의 문자열과 일치하는 경우 memo배열에서 길이에 해당되는 요소를 1로 만들어준다.

  이후에 부분 문자열을 A + A로 나눌 수 있는 경우도 1로 만들어준다.

 

#include <cstdio>
#include <algorithm>
#include <string.h>
using namespace std;

int memo[102];

int main(void)
{
    char s[102] = {0}, a[101][102] = {0, };
    int n, slen, alen[101] = {0, };

    scanf("%s%d", s, &n);
    for(int i = 1; i <= n; ++i){
        scanf("%s", a[i]);
        alen[i] = strlen(a[i]);
    }

    slen = strlen(s);
    for(int i = 1; i <= slen; ++i){
        for(int j = 1; j <= n; ++j){
            char tmp[102] = {0};
            if(i < alen[j])
                continue;
            else if(i == alen[j]){
                strncpy(tmp, s, i);
                if(!strcmp(tmp, a[j])){
                    memo[i] = 1;
                    break;
                }
            }
            else{
                if(!memo[i-alen[j]])
                    continue;
                strncpy(tmp, s+(i-alen[j]), alen[j]);
                if(!strcmp(tmp, a[j])){
                    memo[i] = 1;
                    break;
                }
            }
        }
    }
    printf("%d\n", memo[slen]);
    return 0;
}