블로그 이미지
bro.Yobi

Rss feed Tistory
CSE/SourceCode 2005.05.03 22:09

길찾기(KOI 2002년 1번)

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#define MAX 1000

int A[MAX][MAX];
int T[MAX][MAX];
int L[MAX][MAX];
int R[MAX][MAX];
int N;


int max(int a, int b)
{
        return a>b ? a : b;
}

int main(int argc, char *argv[])
{
        FILE *ifp;
        FILE *ofp;

        int i,j;

//데이터 입력부분
        ifp=fopen("INPUT.TXT","r");

        if(ifp==NULL)
        {
                fprintf(stdout,""INPUT.TXT" doesn't exit.");
                exit(0);
        }

        fscanf(ifp,"%d",&N);
        
        if(N<5)
        {
                fprintf(stdout,"N should be, or be greater than 5");
                exit(0);
        }
        for(i=0;i<N;i++)
        {
                for(j=0;j<N;j++)
                        fscanf(ifp, "%d", &A[i][j]);
        }

        fclose(ifp);



        L[0][0]=A[0][0];
                R[0][0]=INT_MIN;
                T[0][0]=L[0][0];
        for(i=1;i<N;i++)
        {
                L[0][i]=L[0][i-1] + A[0][i];
                                R[0][i]=INT_MIN;
                                T[0][i]=L[0][i];
        }


        for(i=1;i<N;i++)
        {
                        L[i][0]=T[i-1][0]+A[i][0];
                        for(j=1;j<N;j++)
            {
                                L[i][j]=max(L[i][j-1],T[i-1][j])+A[i][j];
                        }                                 
                        R[i][N-1]=T[i-1][N-1]+A[i][N-1];
                        for(j=N-1;j>=0;j--)
                        {
                                R[i][j]=max(R[i][j+1],T[i-1][j])+A[i][j];
                        }                                
                        
                        for(j=0;j<N;j++)
                        {
                                T[i][j]=max(L[i][j],R[i][j]);
                        }
        }
        ofp=fopen("OUTPUT.TXT","w");
        fprintf(ofp,"%d
",T[N-1][N-1]);
        fclose(ofp);

        return 0;
}
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;
}
CSE/SourceCode 2005.04.20 23:58

제목없음

/***********************************
string의 문자들을 순서대로 조합해서
match의 문자열과 같은 문자열을 만들 때,
그 경우의 수를 구하는 문제

예) string : aaaccddd   ,  match : acd 이면
답 : 18
***********************************/

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

#define MAX 100

char string[MAX];
char match[MAX];
int stringlength=0;
int matchlength=0;

int fun( int x,  int y)
{
        int i;

        if(stringlength-x<matchlength-y) return 0;

        if(y==matchlength-1)
        {
                int cnt=0;

                for(i=x;i<stringlength;i++)
                {
                        if(string[i]==match[y])
                        {
                                cnt++;
                        }
                }

                return cnt;
        }
        else
        {
                int sum=0;
                for(i=x;i<stringlength;i++)
                {
                        if(string[i]==match[y])
                        {
                                sum += fun(i+1,y+1);
                        }
                }

                return sum;
        }
}
int main()
{
        int result;

        printf("string을 입력하시오 : ");
        scanf("%s",string);

        printf("match시킬 문자열을 입력하세요 : ");
        scanf("%s",match);

        stringlength=(int)strlen(string);
        matchlength=(int)strlen(match);


        result=fun(0,0);

        printf("%d
", result);
        return 0;

}
CSE/SourceCode 2005.04.18 22:33

Expressions

/******************************************
PC/UVa IDs:110604/10157  
Coded by tuchy@hanmail.net in 2005.04.18
*******************************************/

// CODE BEGINS//

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

int func(int, int);

int main(int argc, char *argv[])
{
        FILE *ifp;

        int length=0;
        int depth=0;

        if(argc!=2 || (ifp=fopen(argv[1], "r"))==NULL)
        {
                fprintf(stderr,"Erorr in reading input file!
");
        }


        while(fscanf(ifp,"%d %d",&length,&depth)!=EOF)
        {
                printf("%d
",func(length, depth));
        }
        fclose(ifp);
}


int func(int l, int d)
{
        if (l==2*d || d==1)
        {
                return 1;
        }
        else
        {
                return 2*func(l-2,d) + func(l-2,d-1);
        }
}

// END OF CODE//
TOTAL 240,276 TODAY 6