백준 1958 LCS 3(c++)

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

1958번: LCS 3

<코드>

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

int main()
{
	vector<vector<vector<int>>>dp(101,vector<vector<int>>(101,vector<int>(101,0)));
	string s1,s2,s3;
	cin>>s1>>s2>>s3;
	for(int i=1;i<=s1.size();i++)
	{
		for(int j=1;j<=s2.size();j++)
		{
			for(int k=1;k<=s3.size();k++)
			{
				if(s1[i-1]==s2[j-1] && s2[j-1]==s3[k-1]){
					dp[i][j][k]=dp[i-1][j-1][k-1]+1;
				}
				else
				{
					dp[i][j][k] = max({dp[i-1][j][k],dp[i][j-1][k],dp[i][j][k-1]});
				}
			}
		}
	}
	cout<<dp[s1.size()][s2.size()][s3.size()];
}

LCS

2022.07.22 - [백준 알고리즘/동적 계획 알고리즘(DP)] - 백준 9251 LCS(c++) 문제에서 2차원 배열이 3차원으로 바뀐 것이 전부이다.

왜냐하면 비교해야할 문자열이 3개이기 때문이다. 알고리즘은 동일한 방식으로 적용시키면 끝이다 !