백준 9251, 9252, 1958 _ LCS 1, 2, 3

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

9251번: LCS

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

9252번: LCS 2

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

1958번: LCS 3

풀이방법

간단하므로 대략적인 내용만 설명하겠다. 자세한 내용은 코드상의 주석을 참고하길 바란다.

 

LCS1은 기본적인 LCS 알고리즘을 사용해서 풀수있다.

LCS2는 위에서 구한 table을 이용해서 역추적하면 된다.

LCS3는 LCS1에서 table을 3차원 배열로만 바꿔주면 풀린다.

---

코드 

 

LCS1

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

int dp[1002][1002];
vector <int> v;
int main(void)
{
	int result = 0;
	string a, b;
	cin >> a >> b;

	a = "0" + a;
	b = "0" + b;

	for (int i = 1; i < (int)b.size(); i++)
	{
		for (int j = 1; j < (int)a.size(); j++)
		{
			//a 와 b 의 알파벳 값이 같을때
			if (b[i] == a[j])
			{
				dp[i][j] = dp[i - 1][j - 1] + 1;
			}
			//다를때
			else
			{
				dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
			}
			result = max(result, dp[i][j]);
		}
	}
	

	cout << result;
	
}

 

LCS2

#include <iostream>	
#include <algorithm>

using namespace std;

int table[1001][1001];
string firstStr;
string secondStr;

int main()
{
	cin >> firstStr >> secondStr;

	firstStr = "0" + firstStr;
	secondStr = "0" + secondStr;

	for (int i = 1; i < firstStr.size(); i++)
	{
		char firstCh = firstStr[i];
		for (int j = 1; j < secondStr.size(); j++)
		{
			char secondCh = secondStr[j];
			//1. 글자가 같을때
			if (firstCh == secondCh)
				table[i][j] = table[i - 1][j - 1] + 1;
			else
				table[i][j] = max(table[i][j - 1], table[i - 1][j]);
		}
	}

	cout << table[firstStr.size() - 1][secondStr.size() - 1] << endl;

	//lcs 역추적
	int row = secondStr.size() -1;
	string ans;
	for (int i = firstStr.size()-1; i > 0; i--)
	{
		for (int j = row; j > 0; j--)
		{
			//1. 왼쪽하고 비교해서 같으면
			if (table[i][j] == table[i][j - 1])
			{
				row--;
			}
			else if (table[i][j] == table[i - 1][j])
			{
				break;
			}
			//2. 다르면 대각선으로
			else
			{
				ans += secondStr[j];
				row--;
				break;
			}
		}
	}
	reverse(begin(ans), end(ans));
	cout << ans << endl;

	return 0;
}

 

LCS3

#include <iostream>	
#include <algorithm>
#include <vector>

using namespace std;

int table[101][101][101];
string firstStr;
string secondStr;
string thirdStr;

int main()
{
	cin >> firstStr >> secondStr >> thirdStr;

	firstStr = "0" + firstStr;
	secondStr = "0" + secondStr;
	thirdStr = "0" + thirdStr;

	for (int i = 1; i < firstStr.size(); i++)
	{
		char firstCh = firstStr[i];
		for (int j = 1; j < secondStr.size(); j++)
		{
			char secondCh = secondStr[j];
			for (int k = 1; k < thirdStr.size(); k++)
			{
				char thirdCh = thirdStr[k];

				//1. 만약에 first, second, thirdch가 다 같으면 i-1, j-1, k-1 에서 +1
				if ((firstCh == secondCh) && (firstCh == thirdCh))
					table[i][j][k] = table[i - 1][j - 1][k - 1] + 1;

				//2. 아니라면 i-1, j, k or i, j-1, k or i, j, k-1 중에서 제일 큰거
				else
					table[i][j][k] = max(max(table[i - 1][j][k], table[i][j - 1][k]), table[i][j][k - 1]);
			}
		}
	}

	cout << table[firstStr.size() - 1][secondStr.size() - 1][thirdStr.size() - 1] << endl;

	return 0;
}

---