[BOJ] 16500번 : 문자열 판별

문제 링크 : 백준 16500번

[문제 접근]

단어 목록에 있는 단어가 문자열 S에 있을 때마다 문자열 S에서 지워주고 갱신하는 방식으로 접근했었는데 이렇게 되면 단어 문자열에 부분 문자열이 존재할 경우 문제가 발생한다.
ex)
software
test
contest
단어 목록이 이렇다고 할 때 test가 s에서 지워지게되면 con만 남게 되므로 만들 수 없다고 판단된다.
따라서 문자열의 길이에 따라 검사해주고 맞다면 index를 해다 문자열 길이 + 1 만큼 해주는 방식으로 코드를 구성했다.

[소스코드]

#include <iostream>
#include <algorithm>

using namespace std;
string s, str[101];
int n;
bool check[101];

void go(int num) {
    if(num == s.size()) {
        cout << 1;
        exit(0);
    }
    if(check[num]) return;
    check[num] = true;
    for(int i=0 ; i<n ; i++) {
        if(s.size()-num<str[i].size()) continue;
        if(str[i] == s.substr(num, str[i].size())) go(num+str[i].size());
    }
}

int main() {
    cin >> s;
    cin >> n;
    for(int i=0 ; i<n ; i++) {
        cin >> str[i];
    }
    go(0);
    cout << 0;
    
	return 0;
}