[백준/C,C++] 9251번: LCS

www.acmicpc.net/problem/9251

9251번: LCS

꽤 많이 애먹었던 문제입니다. 결국 다른 분의 해답을 참고하여 다시 풀어봤지만.. 다음에 이 문제를 다시 풀어본다고 해도 바로 해답이 떠오를 것 같지 않습니다..

	A	C	A	Y	K	P
C	0	1	1	1	1	1
A	1	1	2	2	2	2
P	1	1	2	2	2	3
C	1	2	2	2	2	3
A	1	2	3	3	3	3
K	1	2	3	3	4	4

2차원 배열을 통해 문제를 해결해야 하는데.. 표를 보시면 문자열과 문자열 사이의 LCS의 길이를 나타낸 것입니다. ACAYKP라는 문자열과 C라는 문자열은 LCS가 1입니다. 그리고 그 부분 수열이 최초 등장하는 시점이 0이 1로 바뀌는 시점이죠... 그러니까 문자열 A, C는 서로 LCS가 존재하지 않으나 AC, C는 길이가 1인 LCS가 존재합니다. 서로 같은 문자를 만났을 땐 왼쪽 대각선 위의 값에 +1을, 서로 다른 문자일 경우 바로 왼쪽 또는 위 칸의 값 중 큰 값을 가져오면 됩니다. 예를 들면, 문자열 AC와 CAPCA의 LCS의 길이는 2입니다. 이값은 A와 CAPCA의 LCS의 길이(1) 또는 AC와 CAPC의 LCS의 길이(2) 중 큰 값과 같기 때문에 AC와 CAPCA의 LCS의 길이 또한 2입니다.

#include<iostream>
#include<vector>

using namespace std;

#define MAX 1001

string input[2];
int DP[MAX][MAX];

int main(void)
{
    cin >> input[0] >> input[1];
    int len[2];
    len[0] = input[0].size();
    len[1] = input[1].size();

    for (int i = 1; i <= len[0]; i++) {
        for (int j = 1; j <= len[1]; j++) {
            if (input[0][i - 1] == input[1][j - 1]) {
                DP[i][j] = DP[i - 1][j - 1] + 1;
            }
            else {
                DP[i][j] = max(DP[i - 1][j], DP[i][j - 1]);
            }
        }
    }

    cout << DP[len[0]][len[1]];

    return 0;
}