RESTORE (중상, p. 327)
2025년 11월 16일
내가 상당히 오래 헤매서 난이도를 중에서 중상으로 높였다.
어떻게 풀었나?#
우선 최소 길이 찾는 코드부터 만들었다.
일단 문자열 개수가 15개이니 이걸로 어떻게 dp를 만들까 고민하기 시작.
15밖에 안되니 자연스럽게 bit로 표현해보려 했고, 15bit 상태공간으로 나타내면 이전 상태랑 비교하는게 힘들어서 마지막에 어떤 문자열을 썼는지까지 표현하면 점화식 표현이 가능하다는 것을 바로 캐치함
dp[i][bit] = i번째 문자열을 마지막으로 하면서 지금까지 bit에 해당하는 문자열들을 썼을때 만들어지는 최소 길이
overlap[i][j] = s[i] 다음 s[j]가 올 때 겹치는 알파벳 수
→ 점화식: dp[i][bit] = dp[j][bit^(1<<j)] + s[i].size() - overlap[j][i]
그래서 이제 여기까지 코드로 옮김.
그리고 나서 문자열을 만들면 되겠다고 생각했는데, 너무 시행착오를 많이 겪음
점화식을 재귀적으로 구할 때, s[n] 문자열을 마지막으로 쓰고 지금까지 bit에 해당하는 문자열들을 사용 했을 때, 이 때의 최소길이를 만드는 이전 상태의 문자열들을 Graph로 만듦.
그 부분의 코드가 아래와 같다. Grpah는 배열 v로 표현하려고 했다.
ret = INF;
for(int i=0; i<N; i++) {
if((bit>>i)&1) {
int res = f(i, bit^(1<<i)) + s[n].size() - overlap[i][n];
if(ret > res) {
ret = res;
v[n][bit].clear();
v[n][bit].push_back(i);
}
else if(ret == res) {
v[n][bit].push_back(i);
}
}
}그 외의 문제를 쉽게 구현하는 테크닉 (1가지)#
마지막에 빈 문자열을 집어넣어서 f(N-1, (1«(N-1))-1)만 구하도록 했음. 이 빈 문자열이 없었다면 N번 반복문을 돌면서 f(i, (1«(i-1))-1)을 호출해야 함.
주의할 점#
최소길이를 dp로 구하고 그 최소길이를 만드는 문자열을 만들어 낼 때, bit 상태를 graph만들 때 포함하지 않으면 안됨. 잘 생각해보면, i라는 문자열을 마지막에 썼고, 그 전에 j를 쓸때가 최소라 해서 그 답이 유일할거라 생각할 수 있는데, j를 최소로 만드는 답에 i가 포함되어 있는 경우도 있을 수 있음. 이렇게 되면 i를 최소로 만드는 문자열 중에 i가 있게 되는 오류가 생김.
문제#
정답 코드#
#include <bits/stdc++.h>
using namespace std;
string org_s[16], s[16];
int dp[16][1 << 16];
int overlap[16][16];
bool del[16];
int N;
const int INF = 0x3f3f3f3f;
vector<vector<vector<int>>> v;
int f(int n, int bit) {
if(bit == 0) return s[n].size();
int& ret = dp[n][bit];
if(ret) return ret;
ret = INF;
for(int i = 0; i < N; i++) {
if((bit >> i) & 1) {
int res = f(i, bit ^ (1 << i)) + s[n].size() - overlap[i][n];
if(ret > res) {
ret = res;
v[n][bit].clear();
v[n][bit].push_back(i);
} else if(ret == res) {
v[n][bit].push_back(i);
}
}
}
return ret;
}
string dfs(int n, int bit) {
if(bit == 0) return s[n];
for(int i = 0; i < v[n][bit].size(); i++) {
int y = v[n][bit][i];
if(bit & (1 << y)) {
string ans = dfs(y, bit ^ (1 << y));
if(ans.empty()) continue;
return ans + s[n].substr(overlap[y][n]);
}
}
return s[n];
}
int main() {
int tc;
cin >> tc;
while(tc--) {
int n;
cin >> n;
for(int i = 0; i < n; i++) {
cin >> org_s[i];
}
// 완전히 포함하는 case를 지운다.
memset(del, false, sizeof(del));
for(int i = 0; i < n; i++) {
if(del[i]) continue;
for(int j = 0; j < n; j++) {
if(i == j) continue;
for(int k = 0; k < org_s[i].size(); k++) {
if(strncmp(org_s[i].c_str() + k, org_s[j].c_str(), org_s[j].size()) == 0) {
del[j] = true;
}
}
}
}
N = 0;
for(int i = 0; i < n; i++) {
if(!del[i]) s[N++] = org_s[i];
}
memset(overlap, 0, sizeof(overlap));
for(int i = 0; i < N; i++) {
for(int j = 0; j < N; j++) {
if(i == j) continue;
for(int k = 0; k < s[i].size(); k++) {
if(strncmp(s[i].c_str() + k, s[j].c_str(), s[i].size() - k) == 0) {
overlap[i][j] = s[i].size() - k;
break;
}
}
}
}
s[N++] = "";
memset(dp, 0, sizeof(dp));
v.clear();
v.resize(N + 1, vector<vector<int>>(1 << N, vector<int>()));
f(N - 1, (1 << (N - 1)) - 1);
printf("%s\n", dfs(N - 1, (1 << N - 1) - 1).c_str());
}
return 0;
}책의 풀이법을 참고한 코드#
나는 이전에 정답이 되는 문자열의 최소길이를 구하면서(함수 f()) 나중에 실제 정답인 문자열을 구하기 위한 Graph 배열 v를 만들었는데, 책에선 f() 함수를 똑같이 한번 더 돌면서 실제로 구한 dp값과 동일하면, 그 것이 정답이 되는 문자열임을 이용하여 정답 문자열을 재구성했다. 아래 코드에선 그 함수 이름이 rebuild()이다.
#include <bits/stdc++.h>
using namespace std;
string org_s[16], s[16];
int dp[16][1 << 16];
int overlap[16][16];
bool del[16];
int N;
const int INF = 0x3f3f3f3f;
int f(int n, int bit) {
if(bit == 0) return s[n].size();
int& ret = dp[n][bit];
if(ret) return ret;
ret = INF;
for(int i = 0; i < N; i++) {
if((bit >> i) & 1) {
ret = min(ret, f(i, bit^(1<<i)) + (int)s[n].size() - overlap[i][n]);
}
}
return ret;
}
string rebuild(int n, int bit) {
if(bit==0) {
return s[n];
}
for(int i = 0; i < N; i++) {
if((bit >> i) & 1) {
int res = f(i, bit^(1<<i)) + s[n].size() - overlap[i][n];
if(res == dp[n][bit]) { //i번째 문자열을 사용했을때가 우리가 이미 구한 최적해와 같다면,
return rebuild(i, bit^(1<<i)) + s[n].substr(overlap[i][n]);
}
}
}
return "";//Unreachable Code
}
int main() {
int tc;
cin >> tc;
while(tc--) {
int n;
cin >> n;
for(int i = 0; i < n; i++) {
cin >> org_s[i];
}
// 완전히 포함하는 case를 지운다.
memset(del, false, sizeof(del));
for(int i = 0; i < n; i++) {
if(del[i]) continue;
for(int j = 0; j < n; j++) {
if(i == j) continue;
for(int k = 0; k < org_s[i].size(); k++) {
if(strncmp(org_s[i].c_str() + k, org_s[j].c_str(), org_s[j].size()) == 0) {
del[j] = true;
}
}
}
}
N = 0;
for(int i = 0; i < n; i++) {
if(!del[i]) s[N++] = org_s[i];
}
memset(overlap, 0, sizeof(overlap));
for(int i = 0; i < N; i++) {
for(int j = 0; j < N; j++) {
if(i == j) continue;
for(int k = 0; k < s[i].size(); k++) {
if(strncmp(s[i].c_str() + k, s[j].c_str(), s[i].size() - k) == 0) {
overlap[i][j] = s[i].size() - k;
break;
}
}
}
}
s[N++] = "";
memset(dp, 0, sizeof(dp));
f(N-1, (1<<(N-1))-1);
printf("%s\n", rebuild(N-1, (1<<(N-1))-1).c_str());
}
return 0;
}