[BOJ] 1958 : LCS 3 - travelbeeee

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

---

[알고리즘풀이]

기존의 LCS 문제에서 문자열이 하나 더 추가로 들어온 문제이다.

( 기존 풀이 링크 LCS1 : https://travelbeeee.tistory.com/150 )

( 기존 풀이 링크 LCS2 : https://travelbeeee.tistory.com/151 )

 

입력된 3개의 문자열을 n1 , n2, n3 라고 하자. 또 dp배열을 다음과 같이 정의하자.

dp[i][j][k]

: n1 의 i번 째 문자열, n2의 j번 째 문자열, n3의 k번 째 문자까지 중에서  최장 공통 부분 수열의 길이.

 

그러면 다음과 같은 점화식이 성립한다.

 

1) n1의 i번 째 문자와 n2의 j번 째 문자, n3의 k번 째 문자가 같다면.

   dp[i][j][k] = dp[i-1][j-1][k-1] + 1

   i번 째 문자와 j번 째 문자, k번 째 문자가 같으므로,

   그 전인 (i -1)번 째 문자와 (j - 1)번 째 문자, (k - 1)번 째 문자까지의 길이의 최대 길이에 1을 더해주면 된다.

 

2) 셋 다 같지 않다면.

   dp[i][j][k] = max(dp[i-1][j][k], dp[i][j-1][k], dp[i][j][k-1])

   지금까지 탐색한 가장 큰 값을 저장해주면 된다.

#include<iostream>
#include<string>
#include<algorithm>

using namespace std;

int dp[101][101][101];

int main(void) {
	string n1, n2, n3;
	cin >> n1 >> n2 >> n3;
	int n = n1.length(), m = n2.length(), l = n3.length();

	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++) {
			for (int k = 1; k <= l; k++) {
				if (n1[i - 1] == n2[j - 1] && n2[j - 1] == n3[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], max(dp[i][j - 1][k], dp[i][j][k - 1]));
				}
			}
		}
	cout << dp[n][m][l];

}

---