글
CSE/SourceCode 2005.04.25 23:05돌다리 건너기(KOI 2004년도 1번문제)
/***************************************
일단 recursion으로 풀었음.
2차원 배열을 만들어서 다이나믹프로그래밍으로 바꾸면
좀더 빨라질 것같음.
***************************************/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX 100
char str[2][MAX];
char substr[MAX];
int func(int stNum,int x, int y)
{
int i;
if(x<y||str[stNum][x]!=substr[y])
{
return 0;
}
else
{
if(y==0 )
{
return 1;
}
else
{
int result=0;
for(i=x-1;i>=0;i--)
{
if(str[(stNum+1)%2][i]==substr[y-1])
result+=func((stNum+1)%2,i,y-1);
}
return result;
}
}
}
int main(int argc, char *argv[])
{
int result=0;
int i,j;
int strlength;
int sublength;
printf("string1 : ");
scanf("%s",str[0]);
printf("string2 : ");
scanf("%s",str[1]);
printf("sub string : ");
scanf("%s",substr);
strlength=(int)strlen(str[0]);
sublength=(int)strlen(substr);
for(i=0;i<strlength;i++)
{
result+=func(0,i,sublength-1)+func(1,i,sublength-1);
}
printf("%d
", result);
return 0;
}
일단 recursion으로 풀었음.
2차원 배열을 만들어서 다이나믹프로그래밍으로 바꾸면
좀더 빨라질 것같음.
***************************************/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX 100
char str[2][MAX];
char substr[MAX];
int func(int stNum,int x, int y)
{
int i;
if(x<y||str[stNum][x]!=substr[y])
{
return 0;
}
else
{
if(y==0 )
{
return 1;
}
else
{
int result=0;
for(i=x-1;i>=0;i--)
{
if(str[(stNum+1)%2][i]==substr[y-1])
result+=func((stNum+1)%2,i,y-1);
}
return result;
}
}
}
int main(int argc, char *argv[])
{
int result=0;
int i,j;
int strlength;
int sublength;
printf("string1 : ");
scanf("%s",str[0]);
printf("string2 : ");
scanf("%s",str[1]);
printf("sub string : ");
scanf("%s",substr);
strlength=(int)strlen(str[0]);
sublength=(int)strlen(substr);
for(i=0;i<strlength;i++)
{
result+=func(0,i,sublength-1)+func(1,i,sublength-1);
}
printf("%d
", result);
return 0;
}
RECENT COMMENT