[백준 9252번] LCS 2 (C++)

문제링크 : https://www.acmicpc.net/problem/9252

9252번: LCS 2

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

string s1, s2, result;
int dp[1001][1001];

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);

    cin >> s1 >> s2;
    for(int i=1; i<=s1.size(); i++)
    {
        for(int j=1; j<=s2.size(); j++)
        {
            if(s1[i-1] == s2[j-1])
            {
                dp[i][j] = dp[i-1][j-1] + 1; //문자열의 값이 같다면 대각선위의 값보다 + 1
            }
            else
            {
                dp[i][j] = max(dp[i-1][j], dp[i][j-1]); //왼쪽과 위쪽중 큰 값 선택
            }
        }
    }
    int r = s1.size();
    int c = s2.size();
    while(r>=1 && c>=1) //역추적
    {
        if(dp[r][c] == dp[r-1][c]) r--;
        else if(dp[r][c] == dp[r][c-1]) c--;
        else 
        {
            result += s1[r-1];
            r--;
            c--;
        }
    }
    reverse(result.begin(), result.end());
    if(dp[s1.size()][s2.size()] != 0) cout << dp[s1.size()][s2.size()] << "\n" << result;
    else cout << 0;
    return 0;
}

백준 9251번 LCS 문제에서 해당 문자열까지 출력하도록 한 문제이다.

LCS 길이 구하는 내용은 기존에 풀었던 9251번 문제를 참고하면 된다.

https://blob-thinking.tistory.com/166

[백준 9251번] LCS (C++)

처음에는 string 2차원 배열을 두고, 길이를 구했을 때와 같은 코드로 +1부분만 s1[i-1]을 바꿔서 문자열을 붙이도록 해주었다.

이후 문자열의 길이가 더 긴부분으로 저장하도록 해줬는데 이렇게 푸니 시간초과가 나왔다.

이유를 찾아보니 dp는 원래 매번 값만 비교해서 갱신하는데 string은 string을 대입하는 과정에서 이전 string 자체를 복사하면서 이전 string 길이 만큼의 시간을 잡아먹기 때문에 사실상 O(n^3)의 시간복잡도를 가지게된다는 것을 알게 되었다.

 

이때문에 다른 풀이를 찾아보니 먼저 LCS 길이 dp를 저장하고 역추적 하는 방식을 알게 되었다.

맨 끝부분인 dp[s1.size()][s2.size()]부터 시작하여 역으로 첫 시작점인 1,1 로 돌아가면서 문자열을 저장하게 된다.

기존에 썼던 표를 참고하자면,

	0	A	C	A	Y	K	P
0	0	0	0	0	0	0	0
C	0	C와 A LCS : 0	C와 AC LCS : 1	C와 ACA LCS : 1	C와  ACAY  LCS : 1	C와 ACAYK   LCS : 1	C와 ACAYLP LCS : 1
A	0	CA와 A LCS : 1	CA와 AC LCS : 1	CA와 ACA LCS : 2	CA와 ACAY LCS : 2	CA와 ACAYK LCS : 2	CA와 ACAYKP LCS : 2
P	0	CAP와 A LCS : 1	CAP와 AC LCS : 1	CAP와 ACA LCS : 2	CAP와 ACAY LCS : 2	CAP와 ACAYK LCS : 2	CAP와  ACAYKP LCS : 3
C	0	CAPC와 A LCS : 1	CAPC와 AC LCS : 2	CAPC와  ACA LCS : 2	CAPC와  ACAY LCS : 2	CAPC와  ACAYK LCS : 2	CAPC와  ACAYKP LCS : 3
A	0	CAPCA와 A LCS : 1	CAPCA와  AC LCS : 2	CAPCA와  ACA LCS : 3	CAPCA와  ACAY LCS : 3	CAPCA와  ACAYK LCS : 3	CAPCA와  ACAYKP LCS : 3
K	0	CAPCAK와 A LCS : 1	CAPCAK와 AC LCS : 2	CAPCAK와 ACA LCS : 3	CAPCAK와 ACAY LCS : 3	CAPCAK와 ACAYK LCS : 4	CAPCAK와 ACAYKP LCS : 4

현재 LCS인 dp[r][c]가 dp[r-1][c] 또는 dp[r][c-1과 같을 경우에는 r-- 또는 c--를 하여 뒤로 한칸 이동해준다.

이는 현재 LCS에는 출력하기에 불필요한 값까지 겹치기 때문에 (ACAK, ACAKP) 이를 제거해주는 과정이다.

만약 두가지 모두 같은 경우가 없다면 현재 문자가 LCS를 증가시켜주는 필수 문자이기 때문에 이를 문자열에 저장해주고 r--, c--을 둘 다 해주어 그전 문자열의 길이를 체크해주도록 한다.

첫 시작 : r = 6, c = 6 (LCS = 4)

-> dp[r][c] == dp[r-1][c] 이므로 r-- : r = 5, c = 6 (LCS = 4)

-> 앞서 if 문 모두 해당 안되기에 r--, c-- 과 동시에 문자 저장 (result += s1[r-1]) [K]
r = 4, c = 5 (LCS = 3)

-> dp[r][c] == dp[r-1][c] 이므로 r-- : r = 3, c = 5 (LCS = 3)

-> 앞서 if 문 모두 해당 안되기에 r--, c-- 과 동시에 문자 저장 (result += s1[r-1]) [A]
r = 2, c = 4 (LCS = 2)

->  앞서 if 문 모두 해당 안되기에 r--, c-- 과 동시에 문자 저장 (result += s1[r-1]) [C]
r = 1, c = 3 (LCS = 1)

-> dp[r][c] == dp[r][c-1] 이므로 c-- : r = 1, c = 2 (LCS = 1)

->  앞서 if 문 모두 해당 안되기에 r--, c-- 과 동시에 문자 저장 (result += s1[r-1]) [A]
r = 0, c = 1 (LCS = 0)

 

이를 r과 c가 모두 1이하가 될 때까지 (시작점이 될 때까지) 반복해주며 result에 필수 문자들을 저장해준다.

역추적이므로 문자가 거꾸로 저장되었기에, reverse를 통해서 다시 뒤집어주고 출력해주면 된다.