BOJ 9252 (LCS 2)

• 문제 제목: LCS 2
• 문제 링크: https://www.acmicpc.net/problem/9252

LCS는 Longest Common Subsequence의 약자로 이 문제 제목에도 대놓고 쓰였다. 처음 접했을 때 생각하기 어려운 DP이고, 개같이 멸망. 아래 URL의 풀이를 거의 그대로 참고했다.

• emplam27 님의 정리 글

해당 글에서 설명 방법이 아주 좋은데, 우선 Longest Common String(Substring?)을 먼저 구하는 방법에 대해서 알아보자. “연속된다”는 조건 때문에 이 경우 전체 모양이 아래처럼 된다.

for() {
    for() {
        if (A[a] == B[b]) DP[i][j] = DP[i-1][j-1] + 1;
        else DP[i][j] = 0;
    }
}

사실 모양을 보면 알겠지만 굳이 2차원 DP 배열을 쓸 필요도 없다. 배열에서의 결과는 대각선 방향만 존재한다. 중간에 서로 다른 문자열이 나오자마자 칼같이 0으로 만들어 주는 것이 포인트이다.

여기서 사고를 확장해보자. 0으로 만드는 이유는 연속된다는 조건이 있기 때문이다. 그렇다면 연속된다는 조건이 없을 때는 어떻게 될 것인가? 이 경우 현재까지의 최대 공통 부분 길이가 유지가 되어야 한다. 그리고 이 유지는 x축으로 해야할 수도 있고, y축으로 해야할 수도 있기 때문에 x, y축에 대한 max 값을 구해주면 되겠다. 그래서 위 DP 식이 아주 약간 바뀐다.

for() {
    for() {
        if (A[a] == B[b]) DP[i][j] = DP[i-1][j-1] + 1;
        else DP[i][j] = max(DP[i-1][j], DP[i][j-1]);
    }
}

그리고, 이러한 조건을 만족하는 LCS를 하나 출력하라고 하면, 그것은 DP 배열을 활용해서 대각 방향으로 숫자가 증가하는 path를 잘 따라가면 된다. 결과는 역방향으로 출력하면 된다.

vector<char> word;
int ap = alen, bp = blen;
while(ap != 0 && bp != 0) {
    if (DP[bp][ap] == DP[bp][ap-1]) {
        ap--;
        continue;
    }
    if (DP[bp][ap] == DP[bp-1][ap]) {
        bp--;
        continue;
    }
    word.push_back(A[ap]);
    ap--;
    bp--;
}

if (word.size()) {
    for(auto it = word.rbegin(); it != word.rend(); ++it){  
        printf("%c", *it);
    }
    printf("\n");
}

오늘도 DP에 1패를 했다. 으악!