[백준 9252] LCS 2

https://www.acmicpc.net/problem/9252

---

해설

LCS DP 문제이며, 또 그 이후에 역추적을 사용 해 어떤 문자가 공통 문자열인지 구하는 문제입니다.

 

	0	A	C	A	Y	K	P
0	0	0	0	0	0	0	0
C	0😊	0	1	1	1	1	1
A	0	1😊	1	2	2	2	2
P	0	1😊	1	2	2	2	3
C	0	1	2😊	2	2	2	3
A	0	1	2	3😊	3	3	3
K	0	1	2	3	3	4😊	4

 

공통 문자 수 구하는 건 (https://far-simple.tistory.com/37) 여기서 했으니, 저는 역추적을 설명해보겠습니다.

일단, 😊 이거 적힌 순서대로 for문을 검색해주면 됩니다. 

 

가장 오른쪽 가장 아래에서 부터 시작해서 왼쪽으로 이동합니다.

왼쪽으로 이동하면서 자기보다 왼쪽에 있는 게 자기 숫자랑 다르면 대각선 위로 올라갑니다.

만약, 자기 위에 있는 게 자기랑 숫자가 같으면 그냥 위로 올라갑니다.

올라간 게 0이 될 때 break로 빠져나오면 됩니다.

 

 

˙˙˙

 

소스코드

 

#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
int dp[1001][1001];
int main() {
	string a, b; cin >> a >> b;
	for(int i=1; i<=b.size(); i++)
		for (int j = 1; j <= a.size(); j++) {
			if (a[j - 1] == b[i - 1])
				dp[i][j] = dp[i - 1][j - 1] + 1;
			else
				dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
		}
	int k = a.size();
	string kk;
    
	for (int i = b.size(); i >= 0; i--) {
		if (dp[i][k] == 0)
			break;
		for (int j = k; j >= 0; j--) {
			if (dp[i][j] == dp[i - 1][j])
				break;
			if (dp[i][j] != dp[i][j - 1]) {
				kk += a[j-1];
				k = j - 1;
				break;
			}
		}
	}
	cout << dp[b.size()][a.size()] << '\n';;
	if (dp[b.size()][a.size()] == 0)
		return 0;
	for (int i = kk.size() - 1; i >= 0; i--)
		cout << kk[i];
	cout << '\n';
}