9251번 LCS

 다이나믹 프로그래밍.

 

 예시로 나온 ACAYKP, CAPCAK으로 설명해보자. 첫번째 문자열 시작점을 기준으로 하나씩 비교해서 LCS 길이를 구하게 되면 시간을 초과하게 된다. (이중 for문) 

 

 따라서 DP로 해결하면 된다.

	A	C	A	Y	K	P
C	0
A	1
P	1
C	1
A	1
K	1

 

A를 기준으로 생각해보자.

 1. C를 만났을때 같지 않으므로 0

 2. A를 만났을때 같으므로 1

 3. P를 만났을때 같지 않으므로 0이지만 그 전에 A를 만났으므로 최대값 1

 4. C를 만났을때도 마찬가지 1

 5. A를 만났을때 같으므로 1

 6. K를 만났을때 최대값 1

 

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

C를 기준으로 생각해보자.

 1. C를 만났을때 같으므로 1

 2. A를 만났을때 같지 않으므로 최대값 1

 3. P를 만났을때 같지 않으므로 최대값 1

 4. C를 만났을때 같으므로 그 전을 기준으로 생각해야된다. 무슨 말이냐? A-P와 C-C쪽(빨간 숫자)를 보면 C-C가 만나기 직전에 A-P에서 1이라는 숫자가 적혀있다. 이것은 A-A에서 쭉 내려온 숫자다. 이 말은 A-P까지 'AA'라는 LCS가 있었다는 것이고 C-C를 만났을때 이 경우를 생각해서 +1을 해주는 것이다. 즉, 'AC'라는 LCS가 완성되어 2가 된다.

 5. A를 만났을때 같지 않으므로 최대값 2

    (우리는 현재 최대값을 찾는 것이기 때문에 C-A가 만나기 전 즉 A-A와 C-C(파란 글자)를 비교해 최대값을 넣어주면 된다.)

 6. K를 만났을때 같지 않으므로 최대값 2

 

 이렇게 반복해주면

	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

완성이 된다.

 

ps. 설명이 좀 어렵게 됐는데 실제로 테이블을 그려서 하나씩 계산해보면 이해하기 쉽다.

#include <iostream>
#include <algorithm>
#define MAX 1001
 
using namespace std;
 
string str1;
string str2;
int dp[MAX][MAX];
 
void solved(){
    unsigned long size1=str1.size();
    unsigned long size2=str2.size();
    
    for(int i=1;i<=size1;i++){
        for(int j=1;j<=size2;j++){
            if(str1[i-1]==str2[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[size1][size2];
    
}
 
int main(){
    
    cin >> str1 >> str2;
    
    solved();
}