백준 - LCS 2(9252)

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

9252번: LCS 2

 

LCS문제이다.

기존 알고리즘대로 푼다.

 

행렬 DP를 만들어준다.

 

ACAYKP
CAPCAK

 

      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 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

 

이런 행렬표를 얻게 되고 

LCS값은 4이다.

 

행렬표 끝에서 역추적을 시작해서

dp[y][x] == dp[y][x-1] 라면 왼쪽이동

dp[y][x] == dp[y-1][x] 라면 위로 이동

dp[y][x] != dp[y-1][x-1] 이라면 그때 정답리스트에 넣어준다.

 

 

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

int main() {
	string str_1;
	string str_2;
	
	cin >> str_1;
	cin >> str_2;

	int str_1_size = str_1.size();
	int str_2_size = str_2.size();
	vector<vector<int>> dp(str_2_size + 1, vector<int>(str_1_size + 1, 0));
	for (int i = 1; i <= str_2_size; i++) {
		for (int j = 1; j <= str_1_size; j++) {
			if (str_2[i - 1] == str_1[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[str_2_size][str_1_size] << endl;;
	vector<char> answer;
	int y = str_2_size;
	int x = str_1_size;
	int count = dp[str_2_size][str_1_size];

	while (dp[y][x]) {
		if (dp[y][x] == dp[y][x - 1])
			x -= 1;
		else if (dp[y][x] == dp[y - 1][x])
			y -= 1;
		else {
			answer.push_back(str_2[y-1]);
			y -= 1;
			x -= 1;
		}
	}
	for (int i = answer.size()-1; i >= 0; i--)
		cout << answer[i];	  
	return 0;
	
}