[백준 C++] 9252번: LCS 2

1. 문제

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

9252번: LCS 2

 

2. 알고리즘 분류

• 다이나믹 프로그래밍

 

3. 소스코드

#include <iostream>
#include <algorithm>

using namespace std;

int dp[1003][1003];
string str1, str2;
string str_tmp;

void dfs(int y, int x)
{
	if (dp[y][x] == 0) return;	// LCS 테이블 값이 0이면 끝

	if (dp[y][x] == dp[y - 1][x])	// LCS 테이블 위의 값과 같으면 위로 이동
		dfs(y - 1, x);
	else if (dp[y][x] == dp[y][x - 1])	// LCS 테이블 왼쪽의 값과 같으면 왼쪽으로 이동
		dfs(y, x - 1);
	else    // LCS 위와 왼쪽 값이 다르면, 왼쪽 위 대각선으로 이동
	{
		str_tmp += str1[y - 1];
		dfs(y - 1, x - 1);
		cout << str1[y - 1];
	}
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	// 문자열 2개 입력
	cin >> str1 >> str2;

	// LCS 테이블 채우기
	for (int i = 1; i <= str1.length(); i++)
	{
		for (int j = 1; j <= str2.length(); j++)
		{
			if (str1[i - 1] == str2[j - 1])
				dp[i][j] = dp[i - 1][j - 1] + 1;
			else
				dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
		}
	}

	// LCS 길이 값 출력
	cout << dp[str1.length()][str2.length()] << "\n";

	// LCS 구하기
	dfs(str1.length(), str2.length());

	return 0;
}

 

4. 유용한 문법 / 알고리즘

 1) LCS 길이 구하기

// LCS 테이블 채우기
for (int i = 1; i <= str1.length(); i++)
{
	for (int j = 1; j <= str2.length(); j++)
	{
		if (str1[i - 1] == str2[j - 1])
			dp[i][j] = dp[i - 1][j - 1] + 1;
		else
			dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
	}
}

// LCS 길이 값 출력
cout << dp[str1.length()][str2.length()] << "\n";

 

 2) LCS 구하기

void dfs(int y, int x)
{
	if (dp[y][x] == 0) return;	// LCS 테이블 값이 0이면 끝

	if (dp[y][x] == dp[y - 1][x])	// LCS 테이블 위의 값과 같으면 위로 이동
		dfs(y - 1, x);
	else if (dp[y][x] == dp[y][x - 1])	// LCS 테이블 왼쪽의 값과 같으면 왼쪽으로 이동
		dfs(y, x - 1);
	else    // LCS 위와 왼쪽 값이 다르면, 왼쪽 위 대각선으로 이동
	{
		str_tmp += str1[y - 1];
		dfs(y - 1, x - 1);
		cout << str1[y - 1];
	}
}