글 읽기 - 와일드 카드 문제 도와주세요!

jin8431 5년 전 0

왜 틀렸는지를 모르겠어요ㅠㅠ

#include <stdio.h>
#include <string.h>
char W[100];
char temp[100];
int dp[100][100];

int solve(int a, int b)
{
	int& ret = dp[a][b];

	if (ret != -1)
		return ret;

	if (a == strlen(W))
		if (b == strlen(temp))
			return ret = 1;

	if (a < strlen(W) && b < strlen(temp) && (W[a] == temp[b] || W[a] == '?'))
		return ret = solve(a + 1, b + 1);

	if (W[a] == '*')
		if (solve(a + 1, b) || solve(a, b + 1))
			return ret = 1;

	return ret = 0;

}
int main()
{

	int N;
	scanf("%s", W);
	scanf("%d", &N);
	for (int i = 0; i < N; i++)
	{
		for (int i = 0; i < 100; i++)
			for (int j = 0; j < 100; j++)
				dp[i][j] = -1;
		scanf("%s", temp);
		if (solve(0, 0))
			printf("%s\n", temp);
	}
}

rhs0266 5년 전 2

1) 현재 코드에서 W가 *로 시작한다면 solve(a,b+1) 을 연속적으로 호출하면서 b값이 무한대로 갈 수 있습니다.

2) a, b 값이 모두 100인 경우는 해결 되지만, 둘 중 하나만 100인 경우 dp[100][*] or dp[*][100] 을 접근하는데 이에 해당하는 메모리가 없습니다.

3) 위 문제들을 해결하는 과정에서 strlen(W), strlen(temp)가 많이 호출될 것입니다. strlen() 의 시간 복잡도를 확인해보시고 대안을 생각해보세요.

jin8431 5년 전 0

한동안 안들어 와서 못 봤네요 ㅠㅠ

구체적인 답변 감사합니다!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

와일드 카드 문제 도와주세요!

jin8431 5년 전 0

rhs0266 5년 전 2

jin8431 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말