[백준] 9251.cpp : LCS

www.acmicpc.net/problem/9251

9251번: LCS

---

• 두 문자열을 비교하는 N x N 의 동적 배열을 생성해준다.
• 배열[r][c] 은 해당 문자열의 [0 ~ r] 과 다른 문자열의 [0 ~ c] 까지의 LCS 이다.
• 문자열을 비교해나가면서 같은 문자열이 나올 때 마다 직전 LCS 값에서 1을 더해준다.
• 문자열이 다르더라도, 그 전 까지의 LCS 값은 그대로 유지되기 때문에 값을 똑같이 이어나가준다.
• 다이나믹 프로그래밍은 어디에서나 쓰이는 듯 하다.

---

#include <iostream>
#include <string>

using namespace std;

string a, b;
int answer;
int dp[1001][1001];

int main(void)
{
    cin >> a >> b;
    a = '0' + a;        // 문자열 인덱스를 배열과 똑같이 맞추기 위해서 앞에 쓰레기문자 붙임
    b = '0' + b;
    
    for(int r = 1 ; r < b.size() ; r++)     // 인덱스는 1부터 시작
    {
        for(int c = 1 ; c < a.size() ; c++)
        {
            if(a[c] == b[r]) dp[r][c] = dp[r-1][c-1] + 1;   // 같은 문자가 나오면 직전 LCS 값 + 1
            else dp[r][c] = dp[r][c-1] > dp[r-1][c] ? dp[r][c-1] : dp[r-1][c];  // 아닐 경우 왼쪽 / 위쪽 값 중 큰 값 선택

            if(dp[r][c] > answer) answer = dp[r][c];        // 최대 길이 갱신
        }
    }
    cout << answer << endl;
}