[BAE/<JOON> 문제풀이] 1958. LCS3

폭풍저그머성찡 ㅣ 2020. 6. 5. 14:51

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

 

1958번: LCS 3

첫 줄에는 첫 번째 문자열이, 둘째 줄에는 두 번째 문자열이, 셋째 줄에는 세 번째 문자열이 주어진다. (각 문자열의 길이는 100보다 작거나 같다)

www.acmicpc.net

LCS(LCS(A, B), C)와 LSC(A, B, C)가 다르다는걸 알아야 한다.

 

LCS는 항상 최장 공통 문자열만 찾기 때문에 다음과 같은 반례가 생겨난다.

 

s1 = asdfasdfmeo

s2 = asdfasmeo

s3 = kimmeoseong

 

s1과 s2를 연산하면 asdfas가 검출되므로 마지막의 s3와의 LCS를 구하면 0이 나온다.

 

그래서 3차원 배열로 다시 짰다. 다행히도 공통문자열을 출력하는 문제는 아니라서 2개 문자열 구하는 코드를 보면서

 

3차원으로 확장하면 된다.

 

더보기
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>

using namespace std;

int dp[105][105][105];

int main() {
	string s1, s2, s3;	
	cin >> s1 >> s2 >> s3;
	int l1 = s1.length();
	int l2 = s2.length();
	int l3 = s3.length();
	int mx = 0;
	for (int i = 1; i <= l1; i++) {
		for (int j = 1; j <= l2; j++) {
			for (int k = 1; k <= l3; k++) {
				if (s1[i - 1] == s2[j - 1] && s2[j - 1] == s3[k - 1]) {
					dp[i][j][k] = max({ dp[i - 1][j][k], dp[i][j - 1][k], dp[i - 1][j - 1][k - 1] + 1 });
					if (mx < dp[i][j][k]) {
						mx = dp[i][j][k];
					}
				}
				else {
					dp[i][j][k] = max({ dp[i - 1][j][k], dp[i][j - 1][k], dp[i][j][k - 1] });
				}
			}
		}
	}

	cout << mx;
	return 0;
}