[백준/C++] LCS 3 (No. 1958)

문제

문제 설명

 

 

풀이

 

[문제 풀이]

 

처음에 이 문제를 어떻게 풀 수 있을까 고민을 많이 했다.

단순한 LCS 와 다르게 3개의 문자열에 대한 LCS를 구하는 문제였기 때문이다.

 

처음에는 3중 for문을 이용해 a, b,  c의 문자열이 같은지 비교하고 LCS를 구해 min값을 출력하면 되는 줄 알았지만, 반례가 존재했다.

 

그래서 2개의 문자열만 비교하는 방법을 확장해 문제를 풀었다.

먼저 a, b, c 문자열의 각 i, j, k번을 비교해보자.

 

그리고 LCS[i][j][k]를   a_i, b_j, c_k번 문자열까지 비교한 경우의 LCS라고 가정하자.

 

그러면 a_i, b_j, c_k의 문자가 같은 경우 우리는 a_(i-1), b_(j-1), c(k-1) 번째 문자열까지 비교한 경우의 LCS 깂에서 1이 늘어난 것과 같다는 사실을 알 수 있다.

 

또한 항상 LCS[i][j][k]는 LCS[i-1][j][k], LCS[i][j-1][k], LCS[i][j][k-1] 의 값들 보다 크거나 같아야 된다.

 

왜냐하면 정의에 의해 LCS[i][j][k]는 각 i번, j번, k번 문자열까지 비교한 경우의 LCS 값이기 때문에 LCS[i-1][j][k] 의 값이 3이라면 a의 문자열이 하나 더 추가된 경우의 LCS[i][j][k]의 값은 당연히 3보다 크거나 같을 수 밖에 없다.

 

이를 이용하면 쉽게 LCS 배열을 이용해 문제를 풀 수 있다.

 

LCS배열에 저장하는 값의 정의를 생각하며 아래 그림을 보면 이해가 조금 더 잘 된다.

lcs

 

 

[아이디어 정리]

1. LCS[i][j][k]를 문자열 a, b, c에 대해 i, j, k 번 문자열까지 비교한 경우의 최대 LCS 값으로 정의한다.
2. 정의에 의해 i, j, k번 문자가 같을 경우 LCS[i-1][j-1][k-1]값에 LCS문자가 추가 됐으므로 길이를 1늘린다.
3. 만약 다른 경우에는 이전의 LCS값 들 LCS[i-1][j][k], LCS[i][j-1][k], LCS[i][j][k-1] 중 최대 값을 저장한다.
4. 최종적으로 마지막에 저장된 LCS값을 출력한다.

 

 

Code

 

 

#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;


int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    string a="0", b="0", c="0",str;
    cin >> str;
    a += str;
    cin >> str;
    b += str;
    cin>> str;
    c += str;
    vector<vector<vector<int>>> V(a.size(), vector<vector<int>>(b.size(), vector<int>(c.size(), 0)));
    for (int i=1; i<a.size(); i++)
    {
        for (int j = 1; j < b.size(); j++) 
        {
            for (int k=1; k<c.size(); k++)
            {
                if (a[i]==b[j]&&b[j]==c[k])
                    V[i][j][k] = max(V[i - 1][j - 1][k - 1] + 1, V[i][j][k]);
                else
                    V[i][j][k] = max({ V[i][j][k], V[i - 1][j][k],  V[i][j - 1][k], V[i][j][k - 1] });
            }
        }
    }

    cout << V[a.size()-1][b.size()-1][c.size()-1];
    return 0;
}

---

 

처음에 반례를 생각하지 못하고 아무리 생각해도 맞는 풀이 같아서 해메느라 오래걸렸다...

 

쉬울 것 같았는데... ㅠㅠ

 

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