https://www.acmicpc.net/problem/1958
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;
}
'Algorithm > Algorithm 문제 풀이' 카테고리의 다른 글
[BAE/<JOON> 문제풀이] 9184. 신나는 함수실행 (0) | 2020.06.07 |
---|---|
[BAE/<JOON> 문제풀이] 5582. 공통 부분 문자열 (0) | 2020.06.06 |
[BAE/<JOON> 문제풀이] 1660. 캡틴 이다솜 (0) | 2020.06.04 |
[BAE/<JOON> 문제풀이] 2240. 자두나무 (0) | 2020.06.03 |
[BAE/<JOON> 문제풀이] 5582. 로봇 조종하기 (0) | 2020.06.02 |