[Gold 5] 9251번 LCS

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

9251번: LCS

 

이 문제는 DP를 통해 해결할 수 있다.

 

알고리즘은 다음과 같다.

• 입력된 두 개의 문자열을 비교하면서 LCS(최장 공통 부분 수열)을 찾는 문제로, 가능한 수열을 하나하나 비교하면 시간 초과이기 때문에, dp를 이용하는 문제이다.
• 입력 값으로 표를 만들어 보면 아래와 같은 표가 만들어진다.

	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

 

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

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 

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 

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(NULL);
    cout.tie(NULL);

    string a, b;

    cin >> a >> b;
    
    //1. dp[i][j] = dp[i-1][j-1]+1;
    //2. dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
    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;
}