[[problem:RESTORE]]

문제 1주일째 풀고 있네요.

주로 검산가능한 작은 데이터 위주로
random data로 200개 정도 검토해 보고,
coner case 수정했는데,

계속 오답으로 해매고 있습니다.

물론 최대 최소 긴 데이터들도 테스트해보긴 했구요.

최대한 스스로 풀어보려고 했건만, 몇일동안 못풀고 있어 질문 드립니다.
(iteration DP로 느리진 않을꺼라 생각했는데, 많이 느리기까지 하네요..)

코드 로직은 아래와 같구요.

- cmp(): 문자열 y 뒤에 x가 올때, 겹칠 수 있는 길이를 저장해서 cp[][]에 저장
- slv(): 모든 문자열 조합의 결과가 되는 문자열의 최소 길이를 dp table에 작성
- trk(): dp table에 작성된 최소 조합을 tracking하며 최소 문자열 출력

소스코드는 아래와 같습니다.

~~~ c++

#include

#define ss 15
#define sc 41
#define sr (ss * sc)
#define sf (1 << ss)
#define nf ((1 << ns) - 1)

int tc, ns, at[sc][sc];

char as[ss][sc];

struct cp {
int l, x;
} cp[ss][ss];

struct dp {
int l, t;
} dp[sf][ss];

struct q {
int b[ss], r;
} q;

void read() {
scanf("%d", &ns);

for (int i = 0; i < ns; i++)
    scanf("%s", as[i]);

}

void cmp(int y, int x) {
if (y == x)
return;

int i, j, k;

for (i = 0; as[y][i]; i++) {
    for (j = 0; as[x][j]; j++) {
        at[i][j] = as[y][i] == as[x][j];

        if (i && j)
            at[i][j] += at[i-1][j-1];
    }
}

cp[y][x].l = 0;
cp[y][x].x = -1;

cp[y][y].l = i;
cp[x][x].l = j;

for (k = j-1; k >= 0; k--) {
    if (k == at[i-1][k] - 1) {
        cp[y][x].l = at[i-1][k];
        cp[y][x].x = k;

        break;
    }
}

for (k = i-1; k >= 0; k--) {
    if (j == at[k][j-1]) {
        cp[y][x].l = j;
        cp[y][x].x = j;

        break;
    }
}

}

void cmp() {
for (int y = 0; y < ns; y++)
for (int x = 0; x < ns; x++)
cmp(y, x);
}

int slv() {
for (int i = 0; i < ns; i++)
dp[0][i].l = sr;

for (int f = 1, l, b, t; f <= nf; f++) {
    for (int x = 0; x < ns; x++) {
        if (!(f & (1 << x)))
            continue;

        dp[f][x].t = -1;

        if (b = (f - (1 << x))) {
            dp[f][x].l = sr;
        } else {
            dp[f][x].l = cp[x][x].l;

            continue;
        }

        for (int y = 0; y < ns; y++) {
            if (!(b & (1 << y)))
                continue;

            t = cp[y][y].l == cp[dp[b][y].t][y].l ? dp[b][y].t : y;

            l = dp[b][y].l + cp[x][x].l - cp[t][x].l;

            if (dp[f][x].l > l) {
                dp[f][x].l = l;
                dp[f][x].t = y;
            }

            if (dp[f][x].t == -1)
                dp[f][x].t = y;
        }
    }
}

int m = 0;

for (int i = 1; i < ns; i++)
    if (dp[nf][m].l > dp[nf][i].l)
        m = i;

return m;

}

void trk(int i) {
q.r = -1;

for (int f = nf, t; i != -1; i = t) {
    q.b[++q.r] = i;

    t = dp[f][i].t;

    f -= (1 << i);
}

printf("%s", as[q.b[i = q.r]]);

for (int y, x = 0, j, c = 1; --i >= 0;) {
    if (c)
        y = q.b[i+1];

    x = q.b[i];

    if (c = (cp[y][x].x != cp[y][x].l)) {
        j = cp[y][x].x + 1;

        printf("%s", &as[x][j]);
    }
}

printf("\n");

}

int main() {
for (scanf("%d", &tc); tc--;) {
read();

    cmp();

    trk(slv());
}

return 0;

}
~~~