[백준] 9251: LCS

0. 문제 주소

 

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

9251번: LCS

 

 

1. 풀이

 

문제에서 예시로 준 input을 사용하자.

input :: ACAYKP CAPCAK

 

표로 이해하면 편하다.

 

다음과 같이 2차원 dp 배열을 설계한다.

 

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

 

ACAYKP를 str1, CAPCAK를 str2라고 하자.

i = 1 ~ str1.size() , j = 1 ~ str2.size() 로 순회하며 다음과 같은 규칙으로 테이블을 채워나간다.

 

str1의 i 번째 글자와 str2의 j 번째 글자가 같다면  : dp[i][j] = dp[i-1][j-1] + 1
다르다면 : dp[i][j] = max ( dp[i-1][j] , dp[i][j-1] )

dp[i][j] = (str1의 i번째 글자까지) 와 (str2의 j번째 글자까지) 의 LCS

 

 

직접 채워나가면서 왜 이것이 가능한지 살펴보자. i = 1, j = 1일 때, str1과 str2에서 각각 A와 C가 비교된다. 현재까지 LCS는 0이다.

 

 

 

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

 

i = 1, j = 1일 때, str1과 str2에서 각각 A와 C가 비교된다. 현재까지 LCS는 0이다.

 

 

 

 

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

 

i = 1, j = 2일 땐 각각 A, A가 비교된다. 여기선 dp[i-1][j-1] + 1의 값을 택한다.

 

 

두 문자열에서 같은 문자가 추가되는 상황에선, (str1의 i-1번째 글자까지) 와 (str2의 j-1번째 글자까지)의 LCS에서 1이 추가된다.

즉 밑줄 친 같은 문자인 A가 추가되면서,

(str1의 i-1번째 글자까지) 와 (str2의 j-1번째 글자까지)의 LCS에 A가 붙은 것이라고 생각하면 된다.

 

이번엔 어느 정도 진행한 뒤, 비교할 두 문자가 다른 경우에 대해서 살펴보자.

 

 

 

 

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

 

i = 2, j =5일 땐 각각 C와 A가 비교된다. LCS를 구하고 싶은 문자열은 현재까지 AC // CAPCA 이다.

 

비교할 두 문자가 다른 경우엔 이전까지 저장해뒀던 값들을 이용하여 가장 긴 LCS의 길이를 가져와야 한다.

 

이 경우, 두 문자를 동시에 추가하는 것은 LCS에 영향을 미치지 않으므로,

하나씩 추가해 보는 2가지를 비교하여 큰 값을 가져온다. 다시 말해,

 

A // CAPCA  and  AC // CAPC

 

의 두 가지 중 큰 값을 택한다는 의미다. 두 가지 모두 이미 계산한 값이다.

전자의 경우 dp[1][5] (바로 위), 후자의 경우 dp[2][4] (바로 왼쪽)에 이 값들이 저장되어 있다.

그래서 위에서 언급한

 

다르다면 : dp[i][j] = max ( dp[i-1][j] , dp[i][j-1] )

 

의 규칙으로 테이블을 초기화해야 하는 것이다.

 

 

테이블을 모두 채운 후, 가장 오른쪽 밑에 있는 값이 구하고자 하는 답이다.

 

 

바로 다음 번호에 LCS를 직접 구해야 하는 문제가 있는데, 위와 같이 테이블을 채웠다면 어렵지 않게 구할 수 있다. 다음 글에서 다루겠다.

 

 

2. 풀이 코드

 

* 유의할 점

 

 

#include <bits/stdc++.h>
#define ll long long
#define MAX 1005

using namespace std;

int dp[MAX][MAX];
string str1, str2;

int main(){
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    #endif // ONLINE_JUDGE

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

    cin >> str1 >> str2;

    int str1_size = str1.size();
    int str2_size = str2.size();

    for (int i=0;i<str1_size;i++){
        for (int j=0;j<str2_size;j++){
            char c1 = str1[i], c2 = str2[j];
            if (c1 != c2) {
                dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j]);
            }
            else {
                dp[i+1][j+1] = dp[i][j] + 1;
            }
        }
    }
    printf("%d\n", dp[str1_size][str2_size]);
}