[BOJ / C++] 9251번 : LCS

문제

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

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

입력

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

출력

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

Solved.ac 레벨

골드 V

풀이

LCS, 최장 공통 부분 수열을 찾는 문제였다.

나는 처음 구현 후에 예제 입력을 넣어보니 2가 나왔는데, 이는 연속하는 최장 공통 부분 수열을 구했기 때문이었다.

ACAYKP, CAPCAK에서 연속하는 LCS는 CA밖에 없으니까...

문제에서는 그냥 연속하는 부분수열이기만 하면 되는 거였으니까...

 

아무튼, 문제를 푸는 과정을 또 적어보자.

 

dp[i][j] 2차원 배열을 사용하였다. 

i는 문자열 A, j는 문자열 B의 문자 인덱스를 나타내고, dp[i][j]는 문자열 A의 0번째 ~ i번째 문자, 문자열 B의 0번째 ~ j번째 문자까지의 공통 부분 수열의 길이를 나타낸다.

 

보기 쉽게 표로 나타내보자.

예제 ACAYKP, CAPCAK를 이용한다.

 

dp 배열을 나타내면 아래와 같다. dp 배열의 초기값은 0이다.

j / i	0	1 A	2 C	3 A	4 Y	5 K	6 P
0	0	0	0	0	0	0	0
1 C	0	0	0	0	0	0	0
2 A	0	0	0	0	0	0	0
3 P	0	0	0	0	0	0	0
4 C	0	0	0	0	0	0	0
5 A	0	0	0	0	0	0	0
6 K	0	0	0	0	0	0	0

i, j가 0일때는 0으로 남겨두고, 1일때부터 한 번 LCS를 구하는 과정을 설명해보자.

문자열 A (i)를 기준으로 설명해본다.

 

1. i = 1, 즉 문자열 A의 'A' (A[0] //문자열 인덱스는 0부터이므로 인덱스에서 1을 빼주어야함)

j / i	0	1 A	2 C	3 A	4 Y	5 K	6 P
0	0	0	0	0	0	0	0
1 C	0	0	0	0	0	0	0
2 A	0	1	0	0	0	0	0
3 P	0	1	0	0	0	0	0
4 C	0	1	0	0	0	0	0
5 A	0	1	0	0	0	0	0
6 K	0	1	0	0	0	0	0

문자열 B[0] ~ B[j]를 A[0] 까지와 비교한다.

 

C와 A - LCS 존재 X

CA와 A - LCS는 A, 길이 1

CAP와 A - LCS는 A, 길이 1

CAPC와 A  - LCS는 A, 길이 1

CAPCA와 A- LCS는 A, 길이 1

CAPCAK와 A - LCS는 A, 길이 1

 

2. i = 2, 즉 문자열 A의 'C' (A[1])

j / i	0	1 A	2 C	3 A	4 Y	5 K	6 P
0	0	0	0	0	0	0	0
1 C	0	0	1	0	0	0	0
2 A	0	1	1	0	0	0	0
3 P	0	1	1	0	0	0	0
4 C	0	1	2	0	0	0	0
5 A	0	1	2	0	0	0	0
6 K	0	1	2	0	0	0	0

다시 문자열 B[0] ~ B[j]를 A[0] 까지와 비교한다.

 

C와 AC - LCS는 C, 길이는 1

CA와 AC - LCS는 C, 길이는 1

CAP와 AC - LCS는 A, 길이는 1

CAPC와 AC- LCS는 AC, 길이는 2

CAPCA와 AC - LCS는 AC, 길이는 2

CPACAK와 AC - LCS는 AC, 길이는 2

 

CAPC와 AC를 구하는 과정을 살펴보자.

이전 칸도 동일하고, 현재 칸의 문자가 동일하다면 CAP - AC 간의 LCS의 길이 + 1을 해주는 것을 알 수가 있다.

즉 왼쪽 대각선 위의 칸의 값 + 1이 되는 것을 확인 할 수 있다.

 

3. i = 3, 즉 문자열 A의 'A' (A[2])

j / i	0	1 A	2 C	3 A	4 Y	5 K	6 P
0	0	0	0	0	0	0	0
1 C	0	0	1	1	0	0	0
2 A	0	1	1	2	0	0	0
3 P	0	1	1	2	0	0	0
4 C	0	1	2	2	0	0	0
5 A	0	1	2	3	0	0	0
6 K	0	1	2	3	0	0	0

다시 문자열 B[0] ~ B[j]를 A[0] 까지와 비교한다.

 

C와 ACA - LCS는 C, 길이는 1

CA와 ACA - LCS는 CA, 길이는 2

CAP와 ACA - LCS는 CA, 길이는 2

CAPC와 ACA - LCS는 AC, 길이는 2

CAPCA와 ACA - LCS는 ACA, 길이는 3

CAPCAK와 ACA - LCS는 ACA, 길이는 3

 

값이 그대로 내려오는 경우를 생각해보자.

CAPCA - ACA의 LCS의 길이가 CAPCAK - ACA의 LCS의 길이로 그대로 내려오는 것을 확인할 수 있다.

이는 현재의 왼쪽 칸의 값과 바로 위의 값 중 최대값인 3이 넘어온 것이다.

굳이 LCS가 연속될 필요는 없으므로, 현재까지의 최대값을 넘겨받는 것이다.

 

4. i = 4, 즉 문자열 A의 'Y' (A[3])

j / i	0	1 A	2 C	3 A	4 Y	5 K	6 P
0	0	0	0	0	0	0	0
1 C	0	0	1	1	1	0	0
2 A	0	1	1	2	2	0	0
3 P	0	1	1	2	2	0	0
4 C	0	1	2	2	2	0	0
5 A	0	1	2	3	3	0	0
6 K	0	1	2	3	3	0	0

다시 문자열 B[0] ~ B[j]를 A[0] 까지와 비교한다.

 

C와 ACAY - LCS는 C, 길이는 1

CA와 ACAY - LCS는 CA, 길이는 2

CAP와 ACAY - LCS는 CA, 길이는 2

CAPC와 ACAY - LCS는 CA, 길이는 2

CAPCA와 ACAY - LCS는 ACA, 길이는 3

CAPCAK와 ACAY- LCS는 ACA, 길이는 3

 

5. i = 5, 즉 문자열 A의 'K' (A[4])

j / i	0	1 A	2 C	3 A	4 Y	5 K	6 P
0	0	0	0	0	0	0	0
1 C	0	0	1	1	1	1	0
2 A	0	1	1	2	2	2	0
3 P	0	1	1	2	2	2	0
4 C	0	1	2	2	2	2	0
5 A	0	1	2	3	3	3	0
6 K	0	1	2	3	3	4	0

다시 문자열 B[0] ~ B[j]를 A[4]까지와 비교한다

 

C와 ACAYK - LCS는 C, 길이는 1

CA와 ACAYK - LCS는 CA, 길이는 2

CAP와 ACAYK - LCS는 CA, 길이는 2

CAPC와 ACAYK - LCS는 CA, 길이는 2

CAPCA와 ACAYK - LCS는 ACA, 길이는 3

CAPCAK와 ACAYK - LCS는 ACAK, 길이는 4

 

 

6. i = 6, 즉 문자열 A의 'P' (A[5])

j / i	0	1 A	2 C	3 A	4 Y	5 K	6 P
0	0	0	0	0	0	0	0
1 C	0	0	1	1	1	1	1
2 A	0	1	1	2	2	2	2
3 P	0	1	1	2	2	2	3
4 C	0	1	2	2	2	2	3
5 A	0	1	2	3	3	3	3
6 K	0	1	2	3	3	4	4

다시 문자열 B[0] ~ B[j]를 A[5]까지와 비교한다.

 

C와 ACAYKP - LCS는 C, 길이는 1

CA와 ACAYKP - LCS는 CA, 길이는 2

CAP와 ACAYKP - LCS는 CAP, 길이는 3

CAPC와 ACAYKP - LCS는 CAP, 길이는 3

CAPCA와 ACAYKP - LCS는 CAP, 길이는 3

CAPCAK와 ACAYKP - LCS는 ACAK, 길이는 4

 

위의 과정을 통해 우리는 2가지 조건에 따라 어떤 값을 담아야 하는지 확인할 수 있다.

1. 문자열 B[j]와 A[i]가 같다면, 왼쪽 대각선 위의 칸 값 + 1
dp[i][j] = dp[i - 1][j - 1] + 1

2. 다르다면, 왼쪽 칸 or 바로 위의 값 중 최댓값
dp[i][j] = max(dp[i - 1][j] , dp[i][j - 1])

 

위의 두 점화식과 조건을 토대로 코드를 작성하여 그 중 최댓값을 출력하면 된다.

Code

#include<bits/stdc++.h>

using namespace std;

string s1, s2;
int dp[1001][1001];
int ans = 0;

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

    cin >> s1 >> s2;

    for(int i = 1; i <= s1.length(); i++) {
        for(int j = 1; j <= s2.length(); j++) {
            if(s1[i - 1] == s2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }

    for(int i = 1; i <= s1.length(); i++) {
        for(int j = 1; j <= s2.length(); j++) {
            ans = max(dp[i][j], ans);
        }
    }

    cout << ans << "\n";

    return 0;
}

생각해보니 최댓값은 어차피 dp[s1.length() - 1][s2.length() - 1]에 저장되어 있군....

최댓값을 구하는 과정은 생략이 되어도 되겠다.

9251번: LCS