백준 9251 LCS c++

문제 출처 : www.acmicpc.net/problem/9251

9251번: LCS

문제

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

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

입력

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

출력

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

알고리즘 분류

• 다이나믹 프로그래밍

풀이

입력된 두 개의 문자열을 비교하면서 LCS(최장 공통 부분 수열)을 찾는 문제로, 가능한 수열을 하나하나 비교하면

시간 초과이기 때문에, dp를 이용하는 문제이다.

입력 받은 ACAYKP, CAPCAK로 표를 채워가면서 점화식을 유추해보자.

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

해당 표에 들어가는 값의 의미는, 현재 행까지의 문자열과, 현재 열까지의 문자열 사이의 LCS길이이다.

우선 문자열과 0을 비교했을 때는 당연히 0으로 다 채워주고(0행,0열),

1행(C)부터 채워보자.

C와 A  LCS : 0

C와 AC LCS : C

C와 ACA LCS : C

C와 ACAY LCS : C

C와 ACAYK LCS : C

C와 ACAYKP LCS : C

	0	A	C	A	Y	K	P
0	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
C	0
A	0
K	0

2행(CA)

CA와 A  LCS : A

CA와 AC  LCS : A OR C

CA와 ACA LCS :  CA

CA와 ACAY LCS:  CA

CA와 ACAYK LCS:  CA

CA와 ACAYKP LCS: CA 

 

 

	0	A	C	A	Y	K	P
0	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
A	0
K	0

3행(CAP)

CAP와 A  LCS : A

CAP와 AC  LCS : A OR C

CAP와 ACA LCS :  CA

CAP와 ACAY LCS:  CA

CAP와 ACAYK LCS:  CA

CAP와 ACAYKP LCS: CAP 

	0	A	C	A	Y	K	P
0	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

6행(CAPCAK)

CAPCAK와 A  LCS : A

CAPCAK와 AC  LCS : AC

CAPCAK와 ACA LCS :  ACA

CAPCAK와 ACAY LCS:  ACA

CAPCAK와 ACAYK LCS:  ACAK

CAPCAK와 ACAYKP LCS: ACAK

 

이렇게 채운 표의 규칙을 살펴보면, 두 가지의 규칙이 나온다.

1.해당 칸의 행과 열의 문자가 같을 때는 해당 칸의 왼쪽 대각선의 값에 +1,

2.해당 칸의 행과 열의 문자가 다를 때는 해당 칸의 왼쪽, 위의 값 중 큰 값을 가져온다.

 

이를 점화식으로 세우면

1. dp[i][j] = dp[i-1][j-1]+1;

2. dp[i][j] = max(dp[i-1][j], dp[i][j-1]);

위 식을 가지고 dp를 채워나가고, dp[문자열 a의 길이][문자열 b의 길이]를 출력하면 된다.

코드

#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
int dp[1001][1001];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    string a, b;

    cin >> a >> b;
    for (int i = 1; i <= a.length(); i++) {
        for (int j = 1; j <= b.length(); 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.length()][b.length()];

    return 0;
}