[1958번][C/C++] LCS 3

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

1958번: LCS 3

 

접근

처음에는 LCS가 무조건 이어진 문자열 이어야 한다고 생각해서 이어진 문자열에 대한 코드를 작성했다.

악랄하게도 주어진 예제도 그렇게 이해하고 풀 수 있는 예제였다 ㅠ

예제 입력 abc abc ac

예제 출력 2

a, b가 떨어져있더라도 그냥 띄어서 개수를 셀 수 있다는 것이다..

위와 같은 반례가 있기 때문에 다르게 다 풀고서 처음부터 다시 접근했다.

---

해결

기본적으로 DP로 풀어야한다는 감이 온다. (aka. 직감)

DP[첫번째 문자열에서의 Index][두번째 문자열에서의 Index][세번째 문자열에서의 Index] = 각 문자열의 인덱스에서부터 이전까지의 3개의 문자열의 최대 LCS길이로 설정하고 풀면 된다.

 

예시를 보고 작동을 이해해보자.

a	b	c
a	b	c
a	c

와 같이 2차원 vector v에 문자열 3개가 들어있다.

(DP[0][0][0], DP[1][0][0], DP[0][1][0], DP[0][0][1]은 0으로 놔두고 시작한다.)

 

a	b	c
a	b	c
a	c

v[0][0] == v[1][0] == v[2][0] 이므로 DP[1][1][1] = DP[0][0][0] + 1이다. 

즉, DP[1][1][1] = 1

 

a	b	c
a	b	c
a	c

v[0][0] == v[1][0] != v[2][1] 이므로 DP[1][1][2] = max(DP[0][1][2], DP[1][0][2], DP[1][1][0])

즉, DP[1][1][2] = 0

 

a	b	b
a	b	b
a	c

v[0][0] != v[1][1], v[1][1] != v[2][0] 이므로

DP[1][2][1] = 0

 

 

... 쭉 DP[i][j][k] = 0이 다음과 같이 대입된다.

그러다가

a	b	c
a	b	c
a	c

v[0][2] == v[1][2] == v[2][1] 이므로

DP[3][3][2] = DP[2][2][1] + 1이다.

DP[2][2][1]은 max(DP[1][2][1], DP[2][1][1], DP[2][2][0]) 인데

이 중 DP[1][2][1] = max(DP[0][2][1], DP[1][1][1], DP[1][2][0]) 이다.

마지막으로 DP[1][1][1]은 처음에 구한 1이기 때문에 거슬러 올라가면

DP[3][3][2] = DP[2][2][1] + 1 는

DP[3][3][2] = 2가 된다.

 

즉, 이전에 (i, j ,k) 세 인덱스의 이전 string 3개의 LCS의 최댓값을 저장해서 그 이후 (i, j, k)조합에서 이전을 계산하지 않고 DP값을 이용해서 이후에 이어 붙일 수 있게 구현한 아이디어이다.

---

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <utility>
#include <cmath>

using namespace std;
vector<string> v;
int DP[101][101][101];

bool compare(string a, string b) {
    return a.length() > b.length();
}

int main() {
    string str1, str2, str3;
    cin >> str1 >> str2 >> str3;
    v.push_back(str1);
    v.push_back(str2);
    v.push_back(str3);
    sort(v.begin(), v.end(), compare);
    int len1 = v[0].length(), len2 = v[1].length(), len3 = v[2].length();

    for (int i=1;i<=len1;i++) {
        for (int j=1;j<=len2;j++) {
            for (int k=1;k<=len3;k++) {
                if (v[0][i - 1] == v[1][j - 1] && v[1][j - 1] == v[2][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[len1][len2][len3];
    
    return (0);
}

처음에 이어진 경우만 되는 줄 알고 구현할 때 sort를 이용해서 문자열의 길이를 정렬한 뒤에 풀었던 흔적이 남아있는데 이 로직에서는 의미가 없다. 그냥 v벡터로 구현했기 때문에 남겨준 줄이다.

---

문제가 너무 안 풀려서 오랜만에 다른 사람의 글을 보고 이해해서 푼 문제였다.

DP부분에서는 확실히 내가 약한 것 같다고 느끼고 DP와 문자열문제를 더 풀어야겠다고 생각했다.