백준 9252 LCS2

#include <iostream>
#include <cstring>
#include <string>
#include <algorithm>
using namespace std;
char s1_arr[1001];
char s2_arr[1001];
int memo[1001][1001];

int main() {
	cin >> s1_arr >> s2_arr;
	int s1Size = strlen(s1_arr);
	int s2Size = strlen(s2_arr);
	for (int i = 1; i <= s1Size; i++) {
		for (int j = 1; j <= s2Size; j++) {
			if (s1_arr[i - 1] == s2_arr[j - 1]) {
				memo[i][j] = memo[i - 1][j - 1] + 1;
			}
			else {
				memo[i][j] = max(memo[i][j - 1], memo[i - 1][j]);
			}
		}
	}
	cout << memo[s1Size][s2Size] << endl;

	string result;
	int i = s1Size, j = s2Size;
	while (i > 0 && j > 0) {
		if (memo[i][j - 1] == memo[i - 1][j] && memo[i - 1][j] == memo[i - 1][j - 1] && memo[i - 1][j - 1] == memo[i][j] - 1) {
			result += s1_arr[i - 1];
			i--; 
			j--;
		}
		else {
			if (memo[i - 1][j] == memo[i][j]) {
				i--;
			}
			else if (memo[i][j - 1] == memo[i][j]) {
				j--;
			}
		}
	}
	reverse(result.begin(), result.end());
	cout << result << endl;

	return 0;
}

백준 9251 LCS (http://deque.tistory.com/13)문제에서 메모이제이션한 배열을 역추적하면 답이 나온다.

역추적할때 3가지 경우의 수가 있는데

3 4

4 4 -> 현재 index의 char가 LCS에 포함된다는 뜻이다. 4에서 3으로 대각선으로 index를 올린다

3 4

3 4 -> LCS에 포함되지 않는다. 4에서 4로 index를 올린다

3 3

4 4 -> 위와 마찬가지.

요로코롬 풀었다

끄읏