백준 9251 LCS (C++)

9251번: LCS

동적 프로그래밍을 활용한 최장 공통 부분 수열 구하기 문제이다. 사실 이 문제는 LCS 알고리즘으로 많이 알려져있는 문제이다. 그렇기에 어렵지않게 풀 수 있었다.
문자열의 크기만큼 반복문을 돌면서 같은 문자열을 발견하게 되면, 해당 위치의 LCS 배열에서 + 1한 값을 LCS[i + 1][j+ 1]에 저장해준다. 이렇게하는 이유는 위 표와 같이 문자열 앞에 0을 더해주지 않았기때문에 한칸씩 옮겨서 저장을 해주었다. 같은 문자열이 아니라면 왼쪽, 위쪽중에 큰 값을 LCS[i + 1][j + 1]에 저장해준다. 결국 마지막에는 LCS 최종 값이 저장되어 있게 된다. 이 문제는 어렵지 않게 풀었기에 문제가 없었다.

#include <iostream>
#include <algorithm>

using namespace std;

string A, B;
int LCS[1001][1001];

void solution() {
    for (int i = 0; i < A.size(); i++) {
        for (int j = 0; j < B.size(); j++) {
            if (A[i] == B[j]) {
                LCS[i + 1][j + 1] = LCS[i][j] + 1;
            }
            else {
                LCS[i + 1][j + 1] = max(LCS[i][j + 1], LCS[i + 1][j]);
            }
        }
    }

    cout << LCS[A.size()][B.size()];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> A;
    cin >> B;

    solution();

    return 0;
}