BOJ 백준 1958 : LCS 3

시작하면서

　이번 문제는 최장 공통 부분 수열(LCS:Longest Common Subsequence) 문제이다.

BOJ 1958 - LCS 3

​

문제 이해

​ 해당 문제는 LCS를 문자열 3개에 적용한다. 기본 개념과 동일하게 DP 인덱스를 하나 더 사용하면 된다.

직관적으로 봤을 때에는 A와 B의 LCS를 구하고, 구한 LCS와 C로 한 번 더 LCS를 구하면 되는 것처럼 보인다. 하지만 그렇게 되면 여러 예외가 많이 생기므로 답이 나오지 않으니 주의하자.

참고 링크

​

해결

#include <iostream>
#include <vector>
#include <string>
#include <math.h>

using namespace std;

int main()
{
	vector<vector<vector<int> > > LCSTable;
	int LCSvalue = 0;
	string LCSstring;
	string A, B, C;

	cin >> A >> B >> C;

	LCSTable.resize(A.length() + 1);
	for (int i = 0; i < LCSTable.size(); i++)
	{
		LCSTable[i].resize(B.length() + 1);
		for (int j = 0; j < LCSTable[i].size(); j++)
		{
			LCSTable[i][j].resize(C.length() + 1);
		}
	}

	for (int i = 1; i < LCSTable.size(); i++)
	{
		for (int j = 1; j < LCSTable[i].size(); j++)
		{
			for (int t = 1; t < LCSTable[i][j].size(); t++)
			{
				if (A[i - 1] == B[j - 1] && B[j - 1] == C[t - 1])
				{
					LCSTable[i][j][t] = LCSTable[i - 1][j - 1][t - 1] + 1;
				}
				else
				{
					LCSTable[i][j][t] = max(LCSTable[i - 1][j][t], LCSTable[i][j - 1][t]);
					LCSTable[i][j][t] = max(LCSTable[i][j][t], LCSTable[i][j][t - 1]);
				}
			}
		}
	}

	int firstIndex = LCSTable.size() - 1;
	int secondIndex = LCSTable[firstIndex].size() - 1;
	int thirdIndex = LCSTable[firstIndex][secondIndex].size() - 1;

	LCSvalue = LCSTable[firstIndex][secondIndex][thirdIndex];

	cout << LCSvalue;

	return 0;
}