글 읽기 - 2602 돌다리 건너기 - 시간초과 질문있습니다.

10jobss 6년 전 0

완전탐색으로 시도했는데 70% 정도에서 시간초과가 났습니다.

이 문제는 완전탐색으로 해결 불가능한 문제인가요?

cidx : 두루마리 문자열 인덱스

now : 다리 인덱스

ud : 0 - 악마의 돌다리, 1 - 천사의 돌다리

#include <cstdio>
#include <cstring>
int ans, len_s, len_u, len_d;
char s[21], u[101], d[101];
void solve(int cidx, int now, int ud) {
	switch (ud) {
	case 0:
		if (cidx == len_s) {
			ans++;
			return;
		}
		for (int i = now + 1; i < len_u; i++) {
			if (u[i] == s[cidx]) {
				solve(cidx + 1, i, 1);
			}
		}
		break;
	case 1:
		if (cidx == len_s) {
			ans++;
			return;
		}
		for (int i = now + 1; i < len_d; i++) {
			if (d[i] == s[cidx]) {
				solve(cidx + 1, i, 0);
			}
		}
	}
}
int main() {
	int i, j;
	scanf("%s%s%s", s, u, d);
	len_s = strlen(s), len_u = strlen(u), len_d = strlen(d);
	solve(0, -1, 0);
	solve(0, -1, 1);
	printf("%d", ans);
	return 0;
}