글 읽기 - 종료 조건을 잘못 설정한 것일까요?

oyj9109 7년 전 0

안녕하세요.

입력 문자열을 받는 array의 길이를 20000으로 했더니 런타임 에러가 나고,

100000으로 했더니 시간 초과가 뜹니다.

제 코드에서 length를 구하는 부분이 잘못된 것이 아니라면,

test input 중에 길이가 20000이상인 문자열이 들어오는 것 같은데요.

저는 bottom-up 방식의 dynamic programming을 적용하였는데 시간초과가 납니다.

제가 종료 조건을 잘못 설정한 것인지,

아니면 다른 알고리즘을 사용하여야 하여야 하는 것인지 조언 부탁드립니다!

#include <stdio.h>
#include <stdlib.h>
 
int max (int a, int b) { return a>b? a: b; }
 
int main(void)
{
    char a[100000], b[100000];
     
    while (1) {
        // get input
    int length_a = 0;
    int length_b = 0;
         
        char c=0;
        int eof = 0;
     
    // c가 문자가 아니면 문자가 나올때까지 읽는다.
    while ( !(('0'<=c && c<='9') || ('A'<=c && c<='z')) ) {
        scanf("%c",&c);
        if (c == EOF)
            eof = 1;
    }
     
    // c가 문자이면 array a에 넣는다.
    while (('0'<=c && c<='9')  || ('A' <= c && c <= 'z')) {
        a[length_a++] = c;
        scanf("%c",&c);
    }
 
    if (c == EOF)
        eof = 1;
 
    while ( !(('0'<=c && c<='9') || ('A'<=c && c<='z')) ) {
        scanf("%c",&c);
        if (c == EOF)
            eof = 1;
    }
 
    while (('0'<=c && c<='9')  || ('A' <= c && c <= 'z')) {
        b[length_b++] = c;
        scanf("%c",&c);
    }
 
    if (c == EOF)
        eof = 1;
 
        // Bottom-up tabulation
        int d[length_a][length_b];
        int i, j, m, left, top;
         
        for (i=0; i<length_a; i++) {
            for (j=0; j<length_b; j++) {
                
                // First case
                if (a[i] == b[j]) {
                    d[i][j] = 1;
                    if (i>0 && j>0)
                        d[i][j] += d[i-1][j-1];
                
                // Second case
                } else {
 
                    if (i>0)
                        top = d[i-1][j];
                    else
                        top = 0;
 
                    if(j>0)
                        left = d[i][j-1];
                    else
                        left = 0;
 
                    d[i][j] = max(top, left);
                }
            }
        }
        printf("%d\n",d[length_a-1][length_b-1]);
        if (eof)
            break;
    }   
    return 0;
}

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

문제

문제

출처

ICPC

종료 조건을 잘못 설정한 것일까요?

oyj9109 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말