백준 - 16500번 문자열 판별

문제

단어 목록 A에 있는 여러 단어를 붙여서 문자열 S을 만들 수 있는지 없는지 구하세요

생각

시간 초과

단어 목록을 돌면서 어떤 단어와 문자열의 앞 부분이 일치하는지 보고,
일치하다면, 앞 부분을 제외한 뒤에 남은 부분도 만들 수 있는지 검사한다

void canMake(string s) { //s를 단어 목록에서 만들 수 있는지 검사하는 함수
    for (int i = 0; i < n; i++) { //단어 목록을 돌면서
        bool f = true;
        for (int j = 0; j < word[i].size(); j++) {
            if (word[i][j] != s[j]) {
                f = false;
                break;
            }
        }
        if (f) { //i번째 단어의 모든 부분이 일치하면
            if (word[i].size() == s.size()) {
                result = 1; //크기가 같으면 s를 다 만들었음
            }else{
                canMake(s.substr(word[i].size()));
                //뒤에 남은 부분이 있으면 다시 만들 수 있는지 검사
            }
        }
    }
}

이렇게 하면 시간 초과가 나왔다ㅜㅜ

맞았습니다

질문 검색을 보니까 단어 목록에 substring이 있는 경우
구했던걸 또 구하고 또 구하고.. 그래서 시간 초과가 난다고 한다

예를들어 soft, ware, software, contest 이렇게 주어지면,
soft, ware, contest를 사용해서 혹은 software, contest를 사용해서 만들어지는 경우 등
substring이 있으면 다양한 경우가 만들어지고, 중복으로 검사되고 문제가 있다

근데 나는 그냥 100개 단어 목록 A, 길이 100 이하 S니까
예시가 저렇게 생겨도 당연히 시간초과는 안 나오겠거니 했는데

aaaaaaaaaaaaaaaaaaaaaa...
8
aa
aaa
aaaa
...
이런 예시일 땐 문제가 될 수 도 있겠구나.. 생각했다

그래서 만들었던 조합을 또 만들어서 다시 검사하러 가는 걸 피하고 싶은거니까

앞에서 부터 길이가 i 인 substring은 전에 만들었던 적 있음 을 저장하려고,
check 배열을 만들어서
위와 같은 substring을 만들게 되면
check[i] 값을 1로 바꿔줬다

그리구 어떤 string을 검사할 때
check[string.size()] 값이 1인 경우
이미 만든 적이 있으므로 더 검사하지 않도록 하였다

코드

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <queue>
#include <cmath>

using namespace std;

int n, flag;

string word[105];
int check[105];

void canMake(string s) {
	if (check[s.size()] != 1) {
		if (flag != 1) {
			for (int i = 0; i < n; i++) {
				bool f = true;
				for (int j = 0; j < word[i].size(); j++) {
					if (word[i][j] != s[j]) {
						f = false;
						break;
					}
				}
				if (f) {
					if (word[i].size() == s.size()) {
						flag = 1;
					}
					check[s.size()] = 1;
					canMake(s.substr(word[i].size()));
				}
			}
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);

	string s;
	cin >> s >> n;

	for (int i = 0; i < n; i++) {
		cin >> word[i];
	}

	canMake(s);

	cout << flag;

	return 0;
}