RESTORE문제 질문!

  • 시나브로
    시나브로

    오버랩 계산을 여러번 하는 형식으로 풀었는데,
    책의 예시는 물론 다른 질문에 있는
    1 4 a b c aabcaaaaa 와 같은 것도 잘 되는데 왜 오답이 날까요.. 도저히 모르겠어서 질문해봅니다.

    RESTORE

    // RESTORE 20190225
    // #알고리즘 #프로그래밍 #종만북 #난이도:중
    #include <iostream>
    #include <cstring>
    #include <string>
    #include <vector>
    #include <algorithm>
    #include <cmath>
    #include <cstdio>
    using namespace std;
    template<typename T>
    void vectorclear(vector<T>& vec_obj)
    {vector<T> temp_obj;
    temp_obj.swap(vec_obj);}
    void stringclear(string& str)
    {string throwawaystr;
    str.swap(throwawaystr);}
    //기본셋
    int k;
    vector<string> sts;
    int overlap[15][15];
    int cashe[15][1<<15];
    
    int over(int a,int b)
    {
    int asize=sts[a].size();
    int bsize=sts[b].size();
    for(int i=0;i<asize;i++)    
    {
    for(int j=0;j<asize-i;j++)
    {if(sts[a][i+j]==sts[b][j])
    {if((j==asize-i-1)||((bsize-1)==j)){return overlap[a][b]=j+1;}
    continue;}
     break;}
    }
    return 0;
    }
    //오버랩 함수 , 겹치는 경우를 포함했다.
    
    int restore(int last,int used)
    {
    if(used==((1<<k)-1)){return 0;}
    //기저
    int& ret= cashe[last][used];
    if(ret!=-1){return ret;}
    //메모이제이션
    ret=0;
    for(int next=0;next<k;next++)
    {   
    if((used & 1<<next)==0){
    int ret2=overlap[last][next]+restore(next,used+(1<<next));
    ret=max(ret,ret2);} 
    }
    return ret;
    }
    //최대 오버랩 길이
    
    string recon(int last,int used)
    {
    if(used==((1<<k)-1)){return "";}
    //기저
    for(int next=0;next<k;next++)
    {   
    if(used & (1<<next)) {continue;}
    int ifused = restore(next,used+(1<<next))+overlap[last][next];
    if(restore(last,used)==ifused){return (sts[next].substr(overlap[last][next]) + recon(next,used+(1<<next)));}}
    //overlap 이전을 잘라 버리는 substr. 이것과 맨 처음 글자를 더하면 된다.
    return "!!ops!!";
    }
    
    int main() 
    {
    int C;
    cin>>C;
    while(C--)
    {
    fill(cashe[0],cashe[0]+(15*(1<<15)),-1);
    fill(overlap[0],overlap[0]+15*15,0);
    vectorclear(sts);
    //초기화는 언제나 필수적이다.
    cin>>k;
    int putk=k;
    while(putk--)
    {string a;
    cin>>a;
    sts.push_back(a);
    }   
    //입력끝
    for(int p=0;p<k;p++) 
    {for(int i=0;i<k;i++)
    for(int j=0;j<k;j++)    
    if(i!=j){over(i,j);
    if((over(i,j)==sts[i].size()))  
    {sts[i]=sts[j];}    
    if((over(i,j)==sts[j].size()))
    {sts[j]=sts[i];}
    }
    //오버랩 작성, 겹치는 것 정제 (겹치면 그냥 동일하게 바꾸는 형식) 이걸 반복!
    for(int i=0;i<k;i++)
    for(int j=0;j<k;j++)    
    if(i!=j){over(i,j);}}
    //다시 오버랩 정리.
    int ret3=0;
    for(int m=0;m<k;m++)
    {ret3=max(ret3,restore(m,1<<m));}
    //최대 오버랩 길이 구하기
    for(int m=0;m<k;m++)
    {if(ret3==restore(m,1<<m)) {cout<<sts[m]+recon(m,1<<m)<<endl;break;}
     //최대 오버랩 길이와 restore이 같은 경우가 맨 첫 글자의 m
    }
    }
    return 0; 
    }
    

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