[BOJ] 9251번 : LCS (C++)

https://www.acmicpc.net/problem/9251

9251번: LCS

 

아주 유명한 dp문제이다.

두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중에서 가장 긴 것을 찾아야한다. 

부분 수열이 되어야하므로 공통되는 부분이 연속할 필요는 없다.

가능한 수열을 전부 각각 만들어 비교하게 되면 시간복잡도가 O(2^n*2^m) 으로 너무 느려서 dp를 이용해야한다.

dp를 사용하게 되면 문자열의 길이가 n,m 일 때, 시간복잡도가 O(nm) 이 된다. 

 

풀이는 표를 그리고 최장 공통 부분을 찾아 값을 채우면서 점화식을 유도할 수 있다. 

문제에 나와있는 예제인 ACAYKP, CAPCAK로 표를 만들어보겠다.

그리고 문자열은 인덱스가 0부터 시작하는 0-based 에서 앞에다가 문자열에는 절대 나올 수 없는 '#' 이라는 char을 하나 두면서 1-based로 바꾸어주겠다. 표 기준으로 3번째 줄을 채우려면 'C'와 'A', 'AC', 'ACA', 'ACAY', 'ACAYK', 'ACAYKP' 에서 구할 수 있는 최장 공통 부분의 길이를 써주면 된다.

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

 

표는 다 채우고 나면, 알 수 있는 규칙이 있다. 

1. 두 알파벳이 같아지면, 대각선 위의 숫자에서 +1 된다

2. 두 알파벳이 같지 않으면, 왼쪽칸 혹은 위쪽칸에서 더 큰 값이 오게 된다.

 

이 두 규칙을 바탕으로 코드를 작성하면 된다.

그리고 #을 각 문자열에 붙여주어야 -1인덱스를 만들지 않을 수 있다. 

#include <iostream>
#include <algorithm>
#include <string>
using namespace std;

string s1, s2;
int d[1005][1005];

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin>>s1>>s2;
    int n = s1.size();
    int m = s2.size();

    s1="#"+s1; //0-based to 1-based
    s2="#"+s2;

    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            if(s1[i]==s2[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[n][m];
}