BOJ 9252 - LCS 2
“문자열 DP”
BOJ 9252 - LCS 2
문제 링크
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define rep(i, a, b) for (int i = (a); i < (b); ++i)
const int INF = 0x3f3f3f3f;
using namespace std;
string s1;
string s2;
int dp[1010][1010];
string ans;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
cin>>s1>>s2;
int len1 = s1.length(); // ACAYKP
int len2 = s2.length(); // CAPCAK
for (int i = 1; i <= len1; i++) {
for (int j = 1; j <= len2; j++) {
if (s1[i-1] == s2[j-1])
dp[i][j] = dp[i-1][j-1] + 1;
else
dp[i][j] = max(dp[i][j-1], dp[i-1][j]);
}
}
cout << dp[len1][len2] << '\n';
int x = len1;
int y = len2;
while (x != 0 && y != 0) {
if (dp[x][y] == dp[x-1][y]) {
x -= 1;
} else if (dp[x][y] == dp[x][y-1]) {
y -= 1;
} else {
ans.push_back(s1[x-1]);
x -= 1;
y -= 1;
}
}
reverse(ans.begin(), ans.end());
cout << ans;
return 0;
}
문자열 dp 문제이다. 껄끄러운 주제 + 껄끄러운 주제로 죽음으로 껄끄러운 문제였다. 선행 문제로 LCS를 풀어보아야 한다. 문자열 두 개의 최장 공통 부분 수열(Longest Common Subsequence)을 찾는 요령을 모른다면, 풀어내기가 어려운 문제이다.
LCS의 풀이인 두 문자열의 최장 공통 부분 수열 찾는 대강의 요령은 아래와 같다.
A C A Y K P
0 0 0 0 0 0 0
C 0 0 1 1 1 1 1
A 0 1 1 1 2 2 2
P 0 1 2 2 2 3 3
C 0 1 2 2 2 3 3
A 0 1 2 2 2 3 4
K 0 1 2 3 3 3 4
- 문자열에 대한 이중 배열
dp[N][N]를 채워나가며, 조건에 따라 최장 공통 부분 수열의 길이를 메모해가며 구한다. LCS에서는 이대로dp[len1][len2]를 제출하면 끝이 나지만, LCS 2에서는 그 문자열 중 하나까지 같이 출력해줘야 한다. 이 또한 요령을 모르면 풀기가 쉽지 않을 것으로 생각한다. 아래는 내가 생각한, 아마도 많은 사람들이 처음 봤을 때 생각할 풀이이다.
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define rep(i, a, b) for (int i = (a); i < (b); ++i)
const int INF = 0x3f3f3f3f;
using namespace std;
string s1;
string s2;
string dp[1010][1010];
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
cin>>s1>>s2;
int len1 = s1.length(); // ACAYKP
int len2 = s2.length(); // CAPCAK
for (int i = 1; i <= len1; i++) {
for (int j = 1; j <= len2; j++) {
if (s1[i-1] == s2[j-1]) {
dp[i][j] = dp[i-1][j-1]+ s2[j-1];
} else {
if (dp[i][j-1].length() > dp[i-1][j].length())
dp[i][j] = dp[i][j-1];
else
dp[i][j] = dp[i-1][j];
}
}
}
cout << dp[len1][len2].length() << '\n';
cout << dp[len1][len2];
return 0;
}
기존의 길이를 기록하던
int dp[1010][1010]에, 이제는 문자열 자체를 기록하는string dp[1010][1010]을 만드는 것이다. 직관적으로 보이지 않아서 그런데, 이 코드는 시간 초과가 발생하게 된다. 생각해보면 string도 일종의 배열이고, 그런 관점에서 보면string dp[1010][1010]은 삼중 배열이다. O(N^3)의 시간 복잡도를 가지게 되기 때문에 시간 초과가 발생한다. 최장 공통 부분 수열을 기록하기 위해서는 요령을 알아야 한다.그 요령이 아래 코드이다.
dp[][]배열은 LCS에서 쓰던 것과 동일하다.
while (x != 0 && y != 0) {
if (dp[x][y] == dp[x-1][y]) {
x -= 1;
} else if (dp[x][y] == dp[x][y-1]) {
y -= 1;
} else {
ans.push_back(s1[x-1]);
x -= 1;
y -= 1;
}
}
C A P C A K
0 (0) End 0 0 0 0 0
A 0 0 (1)<- (1) 1 1 1
C 0 1 1 1 (2)<- 2 2
A 0 1 2 2 2 (3)<- 3
Y 0 1 2 2 2 (3) 3
K 0 1 2 2 2 3 (4)<-
P 0 1 2 3 3 3 (4) start
dp[len1][len2] = 4에서dp[len1][len2] = 0이 될 때까지 세 가지 조건에 따라 거슬러 올라가는데, 첫 번째로dp[x][y]가dp[x-1][y]와 동일한가이다. 우 하단에 위 (4)와 아래 (4)가 동일한 것이 보일 것이다. 이것이 첫 번째 경우이다. 이 경우 x를 한 칸 옮겨서 위로 한 칸 이동한다(x -= 1). 두 번째로dp[x][y]가dp[x][y-1]과 동일한가이다. 좌상단을 보면 왼쪽 (1)과 오른쪽 (1)이 동일한 것이 보일 것이다. 이때 오른쪽으로 이동한다(y -= 1). 마지막으로 둘 다 동일하지 않을 때인데, 대각선으로 이동하는 모든 경우이다. 그리고 마지막 경우에만, 이동하는 출발 좌표의 문자를 기록 문자열에 추가한다. 그러면 순서대로 “K”, “A”, “C”, “A”를 가리키고(화살표로 가리키는 좌표) 이를 reverse하면 정답을 얻어낼 수가 있다.이 요령은 알아두는 편이 좋겠다…
