허우적대고있습니다... RESTORE

  • kws4679
    kws4679

    말그대로 어떤게 잘못되었는지도 모른채

    허우적대고 있습니다. 책을 열심히 따라서

    구현했는데도 오답이라고 뜰뿐 무엇이잘못됬는지 모르겠네요

    문제는 RESTORE 입니다.

    #include <iostream>
    #include <vector>
    #include <cstring>
    using namespace std;
    vector<string> in;
    const int MAX_N = 15;
    int k;
    int o[MAX_N][MAX_N], cache[MAX_N][1<<MAX_N];
    int overlap2(string a, string b){
        if(a==b) return a.size();
        for(int i=0; i<a.size(); ++i){
            bool matched = true;
            int j;
            for(j=i; j<min(a.size(),i+b.size()); ++j){
                if(a[j] != b[j-i]) {
                    matched = false;
                    break;
                }
            }
            if(matched) return j-i;
        }
        return 0;
    }
    int overlap(int a, int b){
        int& ret = o[a][b];
        if(ret != -1) return ret;
        return ret = overlap2(in[a],in[b]);
    }
    int restore(int last, int used){
        if(used==(1<<k)-1) return 0;
        int& ret = cache[last][used];
        if(ret != -1) return ret;
        ret = 0;
        for(int i=0; i<in.size(); ++i)
            if((used & 1<<i)==0){
                int cand = overlap(last,i)+restore(i,used+(1<<i));
                ret = max(ret,cand);
            }
        return ret;
    }
    string reconstruct(int last, int used){
        if(used == (1<<k)-1) return "";
        for(int i=0; i<in.size(); ++i){
            if(used & (1<<i)) continue;
            int maxo = restore(i,used+(1<<i))+overlap(last,i);
            if(restore(last,used)==maxo)
                return in[i].substr(overlap(last,i)) + reconstruct(i,used+(1<<i));
        }
        return "";
    }
    
    int main(){
        int c;
        scanf("%d", &c);
        while(c--){
            in = vector<string>();
            memset(cache, -1, sizeof(cache));
            memset(o, -1, sizeof(o));
            scanf("%d", &k);
            for(int i=0; i<k; ++i){
                string s;
                cin >> s;
                bool insert = true;
                for(int j=0;j<in.size();++j){
                    if(overlap2(in[j],s)==s.size()) insert = false;
                    else if(overlap2(s,in[j])==in[j].size()){
                        in[j] = s;
                        insert = false;
                        break;
                    }
                }
                if(insert) in.push_back(s);
            }
            int index=0,length=0;
            for(int i=0;i<in.size();++i)
                if(length < restore(i,1<<i)){
                    length = restore(i,1<<i);
                    index = i;
                }
            string result = in[index] + reconstruct(index,1<<index);
            printf("%s", result.c_str());
        }
        return 0;
    }
    

    초보에게 한줄기 빛을 내려주시길... 부탁드립니다 ^^;


    10년 전
6개의 댓글이 있습니다.
  • kcm1700
    kcm1700
    printf("%s", result.c_str());

    이거 newline 필요할 거 같네요.


    10년 전 link
  • kws4679
    kws4679

    뉴라인을 해도 틀렸다고 나오는군요 흑 ㅠㅠ


    10년 전 link
  • kcm1700
    kcm1700

    k값이 in.size()랑 다르네요.


    10년 전 link
  • kws4679
    kws4679

    옷 그렇군요 k값은 입력값이고 in.size() 는 포함되는것을 제외한 벡터라서 일단 답을 내는데는 문제가 없었군요...

    근데 다시 해봐도 오류라고 나오네요 ㅠㅠ 답변 감사합니다 kcm1700 님


    10년 전 link
  • kcm1700
    kcm1700

    부분문자열 제거 루틴이 부정확하네요.

    1
    4
    a
    b
    c
    aaabcaaaaa


    10년 전 link
  • kws4679
    kws4679

    으아 감사합니다 다시 시도했더니 테스트를 통과하였습니다!!

    으 제가짠 코드를 제가봐도 모르는데 어떻게 찾으셨는지 대단합니다 ㅠㅠ


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