[백준][9252번][C/C++] LCS2

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

9252번: LCS 2

오랜만에 눈물의 AC를 받은 문제이다.

LCS의 길이를 구하는 것 까지는 설명을 듣고 이해할 수 있었다.

하지만 실제 LCS를 구하는 방법에서 막혀서 시간이 걸렸다.

다음과 같은 순서로 LCS를 구하는 문제에 접근했다.

 

1. string2차원 배열을 만들고, DP 배열을 채울 때 string 배열도 DP가 채워짐에 따라서 똑같이 채우는 방법.

하지만 이는 보기 좋기 실패했다.

실패한 이유는 우선 DP는 갱신할 때 매번 단순히 값만 비교해서 갱신하는데 string은 그 이전 string 자체를 복사해오고 뒤에 하나를 덧 붙이는 식으로 짜여지므로 사실상 O(n^3)의 시간복잡도를 가지게 된다. 따라서 시간초과가 나게된다.

또한 컴파일러의 힙 할당 메모리 한계를 초과해서 테스트시에 컴파일 에러가 나기도 했다.

 

2. 완성된 DP 배열의 값을 보고 넣을 문자를 선택하면서 LCS를 완성시키는 방법.

어떻게 DP 배열에서 움직이고, 문자를 LCS에 포함시킬지 판단하는지가 중요한 방법이다.

아래 그림과 함께 과정을 설명하겠다.  그림의 노란 수는 DP[1~len(A)][1~len(B)] 배열 안의 값이다.

2차원 DP 배열을 보고 역추적하는 방법

DP[i = len(A)][j = len(B)] 부터 탐색을 시작해서 (i > 0 && j > 0 == TRUE) 인 동안 역추적을 시행하면 된다.

다음과 같은 규칙으로 움직이며 역추적한다.

모든 규칙에서는 4개의 칸의 값을 확인해서 움직인다.

[1]지금 내가 있는칸, [2]내 왼쪽 칸, [3]내 윗쪽 칸, [4]내 왼쪽 위 대각선 칸

• [1] > [2] == [3] == [4] 인 경우
  
  • [4]로 움직이고 지금내가 있는 칸의 B배열의 값을 LCS에 추가한다.
• [1] == [2] < [3], [4] 인 경우
  • [2]로 움직인다.
• [1] == [3] < [2], [4] 인 경우
  • [3]로 움직인다.
• 그 밖의 경우
  • [3]로 움직인다.

즉 대각선으로 움직일 때만 내가 속한 열의 B[j]값을 LCS에 포함시켜주면 되는 것이다.

결과는 뒤집어서 출력해주면 된다.

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

int main() {
    int DP[1002][1002]; // DP[A의 i번째 글자][B의 j번째 글자] = A의 [0~i]구간으로 탐색했을 때 B의 j번째 글자를 이을 때의 최대 길이
    int lenA, lenB, ans = 0;
    string A, B;
    string ret = "";

    cin >> A;
    cin >> B;
    lenA = A.size();
    lenB = B.size();

    for (int i = 0; i <= lenA; i++) {
        for (int j = 0; j <= lenB; j++) {
            DP[i][j] = 0;
        }
    }

    for (int i = 1; i <= lenA; i++) {
        for (int j = 1; j <= lenB; j++) {
            if (A[i - 1] == B[j - 1]) {
                DP[i][j] = DP[i - 1][j - 1] + 1;
            } else {
                DP[i][j] = max(DP[i - 1][j], DP[i][j - 1]);
            }
        }
    }


//    printf("  ");
//    for (int i = 1; i <= lenB; i++) {
//        printf("%c ", B[i - 1]);
//    }
//    printf("\n");
//    for (int i = 1; i <= lenA; i++) {
//        printf("%c ", A[i - 1]);
//        for (int j = 1; j <= lenB; j++) {
//            printf("%d ", DP[i][j]);
//        }
//        printf("\n");
//    }
//    printf("\n");

    int i = lenA;
    int j = lenB;
    while (i >= 1 && j >= 1) {
        if (DP[i][j] > DP[i - 1][j] && DP[i - 1][j] == DP[i][j - 1] && DP[i][j - 1] == DP[i - 1][j - 1]) {
            ret += B[j - 1];
            i--;
            j--;
        } else if (DP[i - 1][j] > DP[i][j - 1] && DP[i - 1][j] == DP[i][j]) {
            i--;
        } else if (DP[i - 1][j] < DP[i][j - 1] && DP[i][j - 1] == DP[i][j]) {
            j--;
        }
        else {
            j--;
        }
    }

    reverse(ret.begin(), ret.end());

    if (DP[lenA][lenB] != 0)
        cout << DP[lenA][lenB] << "\n" << ret;
    else
        cout << "0";

    return 0;
}