[BOJ] 9252 LCS 2

(2021년 1월 12일에 작성한 글입니다.)

 

주의할 점:

LCS를 복원할 때, dp 값이 왼쪽이나 위쪽과 같은지를 먼저 체크하고

그것에 해당하는 처리를 한 후에

그 둘을 만족하지 않고, dp값이 대각선 위쪽 값 + 1과 같을 때 그것이 LCS 문자열의 구성 요소가 된다.

처음에 대각선 위쪽값+1인지를 먼저 체크했더니 복원이 제대로 안 된다.

​

그리고 나는 dp 파트에서 인덱스랑 string 파트 인덱스가 다른게 싫어서

string s1, s2의 맨 앞에 ' '를 추가했다.

이렇게 처리하고 나면 코드를 이해하기 쉬워져서 좋다.

int main()
{
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	string s1, s2;
	int len1, len2;
	int i, j;

	cin >> s1 >> s2;
	len1 = s1.length(); len2 = s2.length();
	s1 = " " + s1; s2 = " " + s2;

	vector<vector<int>> dp(len1 + 5, vector<int>(len2 + 5));
	for (i = 1; i <= len1; i++) {
		for (j = 1; j <= len2; j++) {
			if (s1[i] == s2[j]) {
				dp[i][j] = dp[i - 1][j - 1] + 1;
			}
			else {
				dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
			}
		}
	}

	cout << *max_element(dp[len1].begin() + 1, dp[len1].begin() + len2 + 1) << ENDL;

	i = len1; j = len2;
	string ans = "";
	while (i && j) {
		if (dp[i][j] == dp[i - 1][j]) {
			i--;
		}
		else if(dp[i][j] == dp[i][j-1]) {
			j--;
		}
		else {
			ans += s1[i];
			i--; j--;
		}
	}

	reverse(ans.begin(), ans.end());
	cout << ans << ENDL;

	return 0;
}