백준 1958 - LCS 3

문제 설명

문자열과 놀기를 세상에서 제일 좋아하는 영식이는 오늘도 문자열 2개의 LCS(Longest Common Subsequence)를 구하고 있었다. 어느 날 영식이는 조교들이 문자열 3개의 LCS를 구하는 것을 보았다. 영식이도 도전해 보았지만 실패하고 말았다.

이제 우리가 할 일은 다음과 같다. 영식이를 도와서 문자열 3개의 LCS를 구하는 프로그램을 작성하라.

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

---

 

 

 

 

 

 

제한 사항

---

 

 

 

 

 

 

풀이

문제를 요약하면, 3개의 문자열의 lcs를 구하는 것이다.

 

해당 문제는 2개의 문자열의 lcs를 구하는 것을 확장시키는 문제이다.

그럼 2개의 문자열의 lcs를 구하는 방법을 알아보자.

2개의 문자열의 lcs를 구하는 방법은 두 문자열의 요소를 하나씩 비교하며 이전에 비교하여 얻은 결과를 활용하는 dp로 해결할 수 있다.

만약 1번 문자열의 i번째 문자와 2번 문자열의 j번째 문자가 같다면 dp[i-1][j-1] + 1이 해당 문자까지의 lcs길이가 된다.

만약 다르다면 dp[i-1][j]와 dp[i][j-1]중 더 큰 값을 선택하면 된다.

이러한 논리를 진행시키려면 초기값을 설정해 주어야 한다.

하지만, 약간의 트릭으로 초기값을 설정할 수 있다.

문자열의 첫번째 자리에 공백을 추가하고 dp의 값이 0으로 초기화한다면 문자열의 실질적인 첫 번째 문자부터 동일한 논리를 적용할 수 있다.

 

이를 3차원으로 확장하면 해당 문제는 해결된다.

한 가지 유의할 점은 문자가 서로 다를 때는 i-1, j-1, k-1과 같이 모든 방향에서 가장 큰 값을 받아와야 한다.

---

 

 

 

 

 

전체 코드

#include <bits/stdc++.h>
using namespace std;
#define INPUT_OPTIMIZE cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
#define INF 2e9

using namespace std;
vector<string> strs(3);
int dp[101][101][101] = { 0, };
int len0, len1, len2;

int main() 
{
	INPUT_OPTIMIZE;

	for (int i = 0; i < 3; i++)
	{
		cin >> strs[i];
		strs[i] = ' ' + strs[i];
	}

	len0 = strs[0].length();
	len1 = strs[1].length();
	len2 = strs[2].length();

	for (int i = 1; i < len0; i++)
	{
		for (int j = 1; j < len1; j++)
		{
			for (int k = 1; k < len2; k++)
			{
				if (strs[0][i] == strs[1][j] && strs[1][j] == strs[2][k])
				{
					dp[i][j][k] = dp[i - 1][j - 1][k - 1] + 1; 
				}
				else
				{
					int result = max(dp[i - 1][j][k], dp[i][j - 1][k]);
					result = max(result, dp[i][j][k - 1]);

					dp[i][j][k] = result;
				}
			}
		}
	}

	cout << dp[len0 - 1][len1 - 1][len2 - 1];

	return 0;
}

---