글 읽기 - 시간 초과 항목입니다.

shfksekdrms2 7년 전 0

start와 end가 들어왔을 때 동적할당을 이용하여 일일이 체크하는 로직입니다.

다른 분들한거보니까 처음 String 입력 받으면 테이블에 미리 계산해놓은걸

Start, end가 들어오면 테이블에서 결과만 출력하게끔 되어 있던데

이러한 방식말고 동적프로그래밍으로 코딩해야한다는 말이 있었습니다.

해당 방식으로 어떻게 접근해야할지 모르겠습니다.

도와 주시면 감사하겠습니다.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int verify(char *str, int start, int end)
{
	int ret=0;
	int i, j=0;
	char *temp, *revers_temp;
	int last = end-start+1;

	temp = (char *)malloc(sizeof(char) * last + 1);
	revers_temp = (char *)malloc(sizeof(char) * last + 1);

	temp[last] = '\0';
	revers_temp[last] = '\0';

	start -= 1;

	for(i=start; i<end; i++)
	{
		temp[j] = str[i];
		j++;
	}

	//revers
	for(i=0; i<last; i++)
	{
		revers_temp[i] = temp[strlen(temp)-i-1];
	}

	if(strcmp(revers_temp, temp) == 0)
	{
		ret=1;
	}
	else
	{
		ret=0;
	}

	//free
	if(temp != NULL)
		free(temp);
	if(revers_temp != NULL)
		free(revers_temp);

	return ret;
}
int main()
{
	int n, m;
	char *str;
	int i;
	int *start, *end;
	char *temp;
	int ret=0;

	scanf("%d", &n);

	str = (char *)malloc(sizeof(char) * n + 1);
	str[n]='\0';

	for(i=0; i<n; i++)
	{
		scanf("%c", &str[i]);
		if(str[i] = ' ')
		{
			scanf("%c", &str[i]);
		}
	}

	scanf("%d", &m);

	start = (int *) malloc(sizeof(int) * m);
	end = (int *) malloc(sizeof(int) * m);

	for(i=0; i<m; i++)
	{
		scanf("%d %d", &start[i], &end[i]);
	}

	for(i=0; i<m; i++)
	{
		ret = verify(str, start[i], end[i]);
		printf("%d\n", ret);
	}

	//free
	if(str != NULL)
		free(str);

	if(start != NULL)
		free(start);

	if(end != NULL)
		free(end);

	return 0;
}

onjo0127 7년 전 0

Manacher's algorithm을 검색해 보시거나, 아니면 (s, e) 구간이 팰린드롬인지의 여부를 저장하는 배열 dp[i][j]를 채울 점화식을 떠올려보셔도 됩니다 ㅎ

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

문제

문제

출처

ICPC

시간 초과 항목입니다.

shfksekdrms2 7년 전 0

onjo0127 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말