🍋 문제링크

1958번: LCS 3

🍎 코드 제출 기록 (메모리 및 시간)

메모리 : 6044KB

시간 : 4ms

🍉 Code

#include <iostream>
#include <algorithm>

std::string str1,str2,str3;
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()
{
	std::cin >> str1 >> str2 >> str3;
}

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

void print_val()
{
	std::cout << dp[str1.size()][str2.size()][str3.size()];
}

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

🥝 메모

• LCS(LCS(str1, str2), str3) 로 하면 안됨...ㅠㅠ
• LCS2 의 코드에서 3차원 배열로 변경만 하면 됨 (3중 for문)

✓ [i-1][j-1][k] 일 때는 안해도 되는건가?