문제
풀이
기존 LCS 문제에서 역추적이 추가된 문제이다. 역으로, 끝에서부터 시작하여, 해당 index에서 위와 왼쪽 값들을 비교하여, 큰 곳으로 이동하고, 만약 위와 왼쪽 값과 해당 인덱스의 값이 모두 다를 때에는 반대로 왼쪽 대각선 위로 올라서 string에 추가를 하여 결과를 도출한다. 코드는 Reference에서 참조하였다.
소스 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <string>
#include <iostream>
using namespace std;
string s1;
string s2;
int d[1001][1001];
int max(int a, int b) {
return (a > b) ? a : b;
}
int main() {
cin >> s1 >> s2;
int n1 = s1.length();
int n2 = s2.length();
//LCS알고리즘을 통해 d배열 작성
for (int i = 1; i <= n1; i++) {
for (int j = 1; j <= n2; j++) {
if (s1.at(i-1) == s2.at(j-1)) {
d[i][j] = d[i - 1][j - 1] + 1;
}
else {
d[i][j] = max(d[i - 1][j], d[i][j - 1]);
}
}
}
cout << d[n1][n2] << endl;
//문자열 추적
int i = n1;
int j = n2;
string res = "";
while (d[i][j] != 0) {
if (d[i][j] == d[i - 1][j] ) {
i--;
}
else if(d[i][j] == d[i][j-1]){
j--;
}
else {
res = s1.at(i-1) + res;
i--;
j--;
}
}
cout << res << endl;
}
//https://2youngjae.tistory.com/77
