1958번: LCS 3

Memo

• LCS 2는 2차원 배열로 푼 반면, LCS 3은 3차원 배열으로 풀었습니다.
• 어렵게 생각하지 않고 LCS 2와 동일한 로직으로 코드를 작성했습니다.

Code

제출 날짜

2021/03/15

메모리

6044 KB

시간

4 ms

#include <iostream>
#include <algorithm>

std::string a,b,c;
int dp[101][101][101];

void input_faster()
{
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(0);
	std::cout.tie(0);
}

void input()
{
	input_faster();
	std::cin >> a >> b >> c;
}

void solve()
{
	for (int i = 1 ; i <= a.size(); i++)
	{
		for (int j = 1 ; j <= b.size(); j++)
		{
			for (int k = 1 ; k <= c.size(); k++)
			{
				if (a[i - 1] == b[j - 1] && b[j - 1] == c[k - 1])
					dp[i][j][k] = dp[i - 1][j - 1][k - 1] + 1;
				else
					dp[i][j][k] = std::max({dp[i - 1][j][k], dp[i][j - 1][k], dp[i][j][k - 1]});
			}
		}
	}
}

void print_val()
{
	std::cout << dp[a.size()][b.size()][c.size()];
}

int main()
{
	input();
	solve();
	print_val();
	return (0);
}