티스토리 뷰

프로그래밍/알고리즘

최대공통부분 수열

터프 프로그래머 2011. 2. 25. 23:40

#include<stdio.h>
#include<string.h>
int p[1005][1005],n,m;
char a[1005],b[1005];
void max(int x, int y, int i, int j)
{
    if(x>y) p[i][j]=x;
    else p[i][j]=y;
}
void input()
{
    FILE *fp=fopen("input.txt","r");
    int i,j;

    fscanf(fp,"%d", &n);
    fscanf(fp,"%s", a);
    fscanf(fp,"%d", &m);
    fscanf(fp,"%s", b);

    for(i=0;i<=n;i++)
    {
        for(j=0;j<=m;j++)
            p[i][j]=0;
    }
    fclose(fp);
}
void prcoess()
{
    FILE *fp1=fopen("output.txt","w");
    int x,y,i,j,cnt=0;
    char g[1005];

    for(i=1;i<=n;i++) // i : b배열
    {
        for(j=1;j<=m;j++) // j : a배열
        {
            max(p[i-1][j],p[i][j-1],i,j);
            if(b[i-1] == a[j-1])
            {
                p[i][j] = p[i-1][j-1]+1;
            }
        }
    }
    cnt=1;
    fprintf(fp1,"%d\n", p[n][m]);   
    x=n;y=m;           
    while(1)
    {
        if(x<1 || y<1 || cnt > p[n][m]) break;

        if(b[x-1]==a[y-1])
        {
            x--;
            y--;
            g[cnt++]=b[x];
            continue;
        }
        if(p[x-1][y]>=p[x][y-1])
        {
            x--;
            continue;
        }
        else if(p[x][y-1]>p[x-1][y])
        {
            y--;
            continue;
        }
    }
    for(i=cnt-1;i>=1;i--)
        fprintf(fp1,"%c", g[i]);
    fprintf(fp1,"\n");
}
void main()
{
    input();
    prcoess();
}

시발 푸느라 힘들었음 ㅠㅠ 근데 90점 나오더라.
채점기 개X끼야 !!

'프로그래밍 > 알고리즘' 카테고리의 다른 글

다익스트라  (0) 2011.06.05
이 글 이전 시간의 글들은 모두 예전 블로그의 포스트들입니다.  (0) 2011.02.25
MAX-SCORE (2009_1)  (0) 2011.02.25
동전교환  (0) 2011.02.25
UVA 231 캐쳐 미사일 검사  (0) 2011.02.25
댓글
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday