wildcard 문제 질문입니다.

  • 아리바
    아리바

    초보적인 질문인거 같은데 ...^ ^
    문제 조건으로 볼 때, 100글자 정도인데
    메모라이즈 하지 않고 그냥 리컬시브로 돌리면 TLE가 나더군요.. (이게 TLE가 아니라 무한루프인줄 알고 무지하게 헤멤)
    푼사람들의 실행타임이 대부분 30ms 미만이라 메모라이즈 안해도 풀릴줄 알았거든요..
    다른 솔루션도 대부분 메모라이즈 한거 같던데..
    엉성하게 짠 랜덤TC를 돌렸을때는 TLE가 안나던데..
    어떤경우에 TLE가 발생하나요?

    [이 글은 과거 홈페이지에서 이전된 글입니다. 원문보기]

    15년 전
4개의 댓글이 있습니다.
  • astein
    astein

    이전에 제출하셨던 소스코드를 올려주시면 반례데이터를 만들어드리겠습... 'ㅅ'


    15년 전 link
  • 아리바
    아리바

    감사합니다. 이러헥 감사할수가
    저의 부끄러운 코드 올리옵니다#include
    #include #include
    #include
    #include
    #include
    #include
    #include
    #include
    #include
    #include
    #include
    #include
    using namespace std;
    #define FOR(i,a,b) for(int i=(a);i<(b);++i)
    #define FORE(i,a,b) for(int i=(a);i<=(b);++i)
    #define REP(i,n) FOR(i,0,n)
    #define REPE(i,n) FORE(i,0,n)
    #define LL long long
    bool check(char* p1, char* p2)
    {
    if(*p1==0)
    {
    if(*p2==0) return true;
    else return false;
    }
    if(*p2==0)
    {
    if(*p1==0 || (*p1=='*'&&*(p1+1)==0) ) return true;
    else return false;
    }
    if(*p1=='*')
    {
    if(*(p1+1)==0) return true;
    while(*p2)
    {
    if(check(p1+1, p2)) return true;
    p2++;
    }
    return false;
    }
    if(*p1=='?' || p1==*p2)
    return check(++p1,++p2);
    return false;
    }
    int main(void)
    {
    #ifdef WIN32
    freopen("input.txt","r",stdin);
    #endif
    int M;scanf("%dn", &M);
    while(M--)
    {
    char wcstr[101] = {0, };
    scanf("%sn", wcstr);
    int N;
    scanf("%dn", &N);
    char str[101];
    vector r;
    REP(i,N)
    {
    scanf("%sn", str);
    char     p1 = wcstr;
    char* p2 = str;
    if(check(p1,p2)==true) r.push_back(str);
    }
    sort(r.begin(), r.end());
    REP(i, r.size())
    {
    printf("%sn", r[i].c_str());
    }
    }
    return 0;
    }


    15년 전 link
  • astein
    astein

    메일주소 알려주시면 메일보내드릴께요... 여기에다가 쓰기엔 좀 ' ' ;;
    (반례 찾았어요)


    15년 전 link
  • 아리바
    아리바

    aribaa555@gmail.com 입니다~


    15년 전 link

  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.