9521 LCS

9521 LCS (c++)

문제

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

접근 방식

LCS

최장 공통 부분 수열 (LCS)는 알고리즘이 있다.
A와 B의 원소를 탐색하므로 문자열의 길이가 N이라면 시간 복잡도는 O(N²)이다.
문제에서 문자열의 최대 길이가 1’000이라고 했으므로 총 연산 수는 1’000’000(백만)이고,
시간 제한은 0.1초 이므로 최대 연산 가능 수는 1초당 약 1억이므로 그 10분의 1인 천만이다.

문제 풀이

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
inline int Max(int a, int b) { return a > b ? a : b; }
string A, B;
int** arr;
void Init()
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> A >> B;
    arr = new int* [A.length() + 1];
    for (int i = 0; i <= A.length(); ++i)
    {
        arr[i] = new int[B.length() + 1];
        fill(arr[i], arr[i] + B.length() + 1, 0);
    }
}
void Solve()
{
    for (int i = 1; i <= A.length(); ++i)
    {
        for (int j = 1; j <= B.length(); ++j)
        {
            if (A[i - 1] == B[j - 1]) arr[i][j] = arr[i - 1][j - 1] + 1;
            else arr[i][j] = Max(arr[i - 1][j], arr[i][j - 1]);
        }
    }
    cout << arr[A.length()][B.length()] << endl;
}
void Delete()
{
    for (int i = 0; i <= A.length(); ++i)
    {
        delete[] arr[i];
    }
    delete[] arr;
}
int main() {
    Init(); Solve(); Delete();
}

다시 생각해 볼 점

1. LCS는 쪼갤 수 없는 배낭 문제와 닮았다. (DP로 최적화가 더 가능할 것 같다.)