6개의 댓글이 있습니다.
-
-
shinhj88 -
아~~ 틀린점은 경로를 구할때 경로 중간에 완전히 포함되는 문자열이 있다면 그 완전히 포함되는 문자열 다음에 나오는 경로를 출력할때 완전히 포함되는 경로를 지우는 경우가 생가셔 오답이 나왔었습니다.
예를 들어 a abc abd이런 데이터일때 abcabd가 답인데 abcbd이렇게 나왔습니다 즉 경로가 2 1 3인데 2 1경로까지는 문제가 안되는데 1 3 인경우 a를 제외하고 bd가 출력되는데 a는 두번째 문자열의 완전히 포함되는 단어이기때문에 문제가 되서 경로를 저장하는 배열을 수정하여 해결 하였스빈다. ㅋㅋㅋㅋㅋㅋ 글로쓰기 힘드네요 ㅋㅋㅋ 좋은책 써주신 종만님 존경합니다.ㅋㅋㅋㅋㅋ
13년 전 link
-
-
정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
shinhj88
실험데이터 복구하기 문제를 풀고 있는데
여러 테스트 데이터를 넣어 보았는데 잘못된점을 찾지 못하였습니다.
고수님들이 좀 도와주세요 ㅜㅜ
제가 푼방법은
a배열에는 i번째 단어 다음에 j번째 단어가 왔을때 몇개의 단어가 추가 되는지를 저장하고 추가되는 문자도 함께 저장했습니다.
그다음 외판원문제처럼 총 길이가 최소가 되도록 하는 경로를 구하였습니다.
글쓰는것에 서툴러서 제가 푼 풀이가 잘 전달됬는지 모르겠습니다.ㅠㅠ
도와주세요ㅠㅠ
~~~ c++
#include
#include
#include
#include
int n;
struct calData{
int velue;
char printstring[100];
}a[16][16],seta,data[16];
int D[16][(1<<16)+1];
int MAX;
int P[16][1<<16];
void input()
{
int i;
scanf("%d",&n);
MAX=0;
for(i=1;i<=n;i++)
{
scanf("%s",data[i].printstring);
data[i].velue=strlen(data[i].printstring);
MAX+=data[i].velue;
}
MAX++;
}
calData cal(calData A,calData B)
{
int i,j,k;
bool flag=false;
calData temp;
temp.velue=0;
temp.printstring[0]=NULL;
//strcpy(temp.printstring,data[I]);
for(i=0;i<A.velue;i++)
{
k=i;
flag=false;
for(j=0;j<B.velue;j++)
{
if(k==A.velue)break;
if(A.printstring[k]!=B.printstring[j]){
flag=true;
break;
}
k++;
}
if(!flag)
{
for(k=j;k<B.velue;k++)
{
temp.printstring[temp.velue++]=B.printstring[k];
}
temp.printstring[temp.velue]=NULL;
return temp;
}
}
temp.velue=B.velue;
strcpy(temp.printstring,B.printstring);
return temp;
}
void mkdata()
{
int i,j;
calData t;
for(i=1;i<=n;i++)
{
a[0][i]=data[i];
for(j=1;j<=n;j++)
{
if(i==j)
{
a[i][j].velue=0;
a[i][j].printstring[0]=NULL;
continue;
}
t=cal(data[i],data[j]);
a[i][j]=t;
}
}
}
{
m=a[now][i].velue;
{
int TSP(int check,int now)
{
int i,t,m;
if((1<<(n+1))-1==check)
{
return 0;
}
if(D[now][check]!=-1)return D[now][check];
D[now][check]=MAX;
for(i=1;i<=n;i++)
{
if(!(check&(1<
t=TSP(check+(1<
for(int j=1;j<=n;j++)
{
if((check&(1<
m=0;
break;
}
}
t+=m;
if(D[now][check]>t)
{
D[now][check]=t;
P[now][check]=i;
}
}
void output(int now,int check)
{
bool flag=true;
while(1)
{
flag=true;
int to=P[now][check];
for(int i=1;i<=n;i++)
{
if((check&(1<<i))&&a[i][to].velue==0)
{
flag=false;
break;
}
}
check+=1<<P[now][check];
if(flag==true)
{
for(int i=0;i<a[now][to].velue;i++)
{
printf("%c",a[now][to].printstring[i]);
}
}
now=to;
if(check==(1<<(n+1))-1)break;
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
memset(D,-1,sizeof(D));
memset(P,0,sizeof(P));
input();
mkdata();
TSP(1,0);
output(0,1);
}
13년 전