[백준 9251] LCS C++

www.acmicpc.net/problem/9251

9251번: LCS

최대공통부분 수열의 문제입니다.

 

처음에 용어가 헷갈렸는데,

LCS는 2가지의 용어가 있습니다.

1. LCS (Longest Common Substring) 최대공통부분문자열

2. LCS (Longest Common Subseqeunce) 최대공통부분수열

입니다.

 

둘의 큰 차이는 연속하냐 안하냐의 차이인데, 문자열의 경우 연속하는 문자열중 최대의 공통 부분 문자열이고,

수열은, 연속하지 않지만, 최대의 공통 부분의 문자를 찾는 것이 핵심입니다.

 

두 개의 문자열을 이 중 for문으로 하나씩 접근하면서,

문자 a[i-1], 문자 b[j-1] 가 같을 때 dp[i][j] = dp[i-1][j-1] + 1을 하여

같은 문자 개수 1개를 추가합니다. 

 

두 개의 문자가 같지 않을 때 i,j인덱스의 왼쪽, 위쪽 중에 최댓값을 취하는 이유는,

두 문자를 각 각 포함하지 않은 DP의 값에서 1을 더해주어야 하기 때문입니다.

	A	C	A	Y	K	P
C	0	0	0	0	0	0	0
A	0	0	1 DP[i-1][j-1]	1	1	1	1
P	0	1	1	2 DP[i][j]	2	2	2
C	0	1	1	2	2	2	3
A	0	1	2	2	2	2	3
K	0	1	2	3	3	3	3
	0	1	2	3	3	4	정답4

 

dp[i][j]의 의미는 i, j 인덱스 이전 까지의 LCS를 뜻합니다.

그리고, 만약 a[i-1], b[i-1]문자가 같지 않다면, 

dp[i-1][j]나, dp[i][j-1]에서 가장 큰값을 dp[i][j] 값에 그대로 복사하며 되겠습니다.

즉, a[i-1] 이나 b[i-1] 까지 공통 부분 문자 수열의 최대 값을 복사하시면 됩니다. 

 

#include <iostream>
#include <algorithm>
#include <string>

using namespace std;

const int MAX = 1001;

int dp[MAX][MAX];


void solution(){

    string a, b;
    cin >> a >> b;

    int a_size = a.length();
    int b_size = b.length();

    for (int i = 1; i <= a_size; i++)
        for (int j = 1; j <= b_size; j++){
            if (a[i-1] == b[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[a_size][b_size] << '\n';
    


}
int main(){

    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    solution();

    return 0;
}