BOJ 9251 LCS(C++)

LCS 성공

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	128 MB	2084	932	661	42.728%

문제

LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.

예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.

입력

첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다.

출력

첫째 줄에 입력으로 주어진 두 문자열의 LCS의 길이를 출력한다.

예제 입력 

ACAYKP
CAPCAK

예제 출력 

4

힌트

출처

• 문제를 만든 사람: baekjoon

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33

#include    <string> #include    <iostream> #pragma warning(disable:4996) #define max(x,y) ((x) < (y) ? (y) : (x)) using namespace std; int D[1111][1111];   int main() {     ios::sync_with_stdio(false);     string A, B;     cin >> A >> B;       D[0][0] = (A[0] == B[0]);     for (int i = 1; i < A.length(); ++i)         D[i][0] = max(D[i - 1][0], (A[i] == B[0]));     for (int i = 1; i < B.length(); ++i)         D[0][i] = max(D[0][i - 1], (A[0] == B[i]));     for (int i = 1; i < A.length(); ++i)     {         for (int j = 1; j < B.length(); ++j)         {             if (A[i] == B[j])                 D[i][j] = D[i - 1][j - 1] + 1;             else                 D[i][j] = max(D[i - 1][j], D[i][j - 1]);         }     }       cout << D[A.length() - 1][B.length() - 1] << endl;       return 0; }

유명한 문제라고 들었다. 

다이나믹 프로그래밍으로 해결. 

기본적인 점화식은 다음과 같다. 

I길이의 A수열과

J길이의 B수열이 있을 때

A의 i번째, B의 j번째까지의 최장공통부분수열(LCS)는 

D[i][j]로 나타내고 이는 두가지로 나눌 수 있다. 

1. A[i]번째와 B[j]번째가 동일한 경우 

D[i-1][j-1] + 1이 된다. A[i]와 B[j]가 동일하기 때문에 그 이전까지의 최대값 + 1이 i,j번째까지의 최대값이 된다.

2. A[i]번째와 B[j]번째가 동일하지 않은 경우

이 경우에는 D[i][j-1]과 A[i-1][j] 중 큰 값이 오게 된다. D[i-1][j-1]은 이미 D[i][j-1], D[i-1][j]에서 고려되었기 때문에 두 후보 중에 더 큰 값을 선택하면 된다. 

사실 이 문제에서 어렵게 느껴졌던 것은 14~18라인 이었는데

특히 14라인의 D[0][0]을 초기화하지 않아서 왜 틀린지도 모르고 멘붕이었다. 

이건 구현상의 문제이므로 문제를 푸는 사람에 따라 for loop 내에서 자동으로 연산될 수도 있겠지만... 

15~18라인은  

초기화 부분인데 A[0]과 B전체, B[0]과 A전체를 비교해서 미리 계산을 해두어야 한다. 

그래야 19라인의 for loop에서 계산이 가능하다. 

생각해보면 간단한데

19라인의 for loop는 

i-1, j-1을 참조하므로 

 for (int i = 1; i < A.length(); ++i)

        for (int j = 1; j < B.length(); ++j)

        

위와 같이 1부터 시작할수밖에 없다. 

그렇다면 0번째를 계산해야 하고 자연스럽게 15~18라인을 먼저 계산해주어야 한다.

그외에는 다른 다이나믹 문제와 크게 다를게 없다.