[BOJ / C++] 9252번 : LCS 2

문제

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

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

입력

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

출력

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

LCS가 여러 가지인 경우에는 아무거나 출력하고, LCS의 길이가 0인 경우에는 둘째 줄을 출력하지 않는다.

Solved.ac 레벨

골드 IV

풀이

먼저 이 문제를 풀려면 9251번 : LCS 문제를 풀면 좋다. 이 문제에다가 살만 더 붙이면 되기 때문이다.

9251번: LCS

내 9251번 : LCS 문제의 풀이는 이곳으로.

[BOJ / C++] 9251번 : LCS

 

위 풀이의 표, 최종본을 가져와봤다.

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

우리가 가져와야 하는 부분은 dp[i][j]의 값이 처음 변화하는 부분이다. 색깔로 표시한 부분의 문자를 가져와야 한다는 뜻이다.

맨 마지막 칸 부터 LCS의 길이를 줄여나가며 탐색한다.

 

1. 바로 왼쪽 칸과 값이 같은 경우.

처음 탐색을 시작하면 maxLen의 값은 LCS의 길이 4이다.

dp[6][6]의 바로 왼쪽 값인 dp[5][6]이 4로 동일하므로 dp[6][6]은 값이 처음 변화하는 부분이 아니다.

j = 6으로 고정하고 i를 1 감소시키며 왼쪽 칸으로 넘어간다.

 

2. 바로 윗쪽 칸과 값이 같은 경우.

LCS를 구할 때 s1[i]와 s2[j]가 다르다면 왼쪽 대각선 위의 값과 바로 위의 값을 비교하여 최대값을 받아 내려적게 된다.

따라서 바로 뒷족 칸과 값이 같은 경우도 처음으로 값이 변화하는 부분이 아니다.

이 때는 왼쪽, 윗쪽으로 이동할 수 있게 i, j 두 값을 모두 변화시킨다.

 

3. 바로 윗쪽 칸과 바로 왼쪽 칸의 값이 다를 경우.

dp[5][6]을 보자. dp[5][6]은 4이고 바로 윗쪽 칸인 dp[5][5]와 dp[4][6]의 값은 3으로 dp[5][6]과 다르다. 따라서 dp[5][6]의 값은 처음 값이 변화된 부분이다. 따라서 s1[5 - 1]을 정답 문자열에 추가시킨다.

 

위 세 과정을 반복하며 탐색하면 우리가 구한 LCS의 길이에 해당하는 문자열을 구할 수 있다.

 

 

Code

#include<bits/stdc++.h>

using namespace std;

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

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]);
            }
        }
    }

    maxLen = dp[s1.length()][s2.length()];

    cout << maxLen << "\n";

    int tmp = s2.length(); //s2 문자열의 길이로 초기화
    for(int i = s1.length(); i >= 1; i--) {
        for(int j = tmp; j >= 1; j--) {
            if(dp[i][j] == dp[i - 1][j]) {
            	//바로 왼쪽 칸과 동일하다면 위아래 방향은 현재로 고정 후 왼쪽 칸으로 넘어간다..
                tmp = j;
                break;
            } else if(dp[i][j] == dp[i][j - 1]) {
            	//바로 위쪽 칸과 동일하다면 그냥 지나쳐도 좋다.
                continue;
            } else {
            	//왼쪽 칸, 위쪽 칸과 다르면 값이 처음 바뀌는 부분이다.
                //s1 문자열의 i - 1번째를 정답 문자열에 추가한다.
                ans.push_back(s1[i - 1]);
            }
        }
    }
	
    //역순으로 들어가있으므로 뒤집어서 출력한다.
    reverse(ans.begin(), ans.end());


    cout << ans << "\n";

    return 0;
}

9252번: LCS 2