[백준/C++] 9251번: LCS(G5)

문제

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

9251번: LCS

 

 

사용한 알고리즘

2022.01.19 - [PS/Algorithm] - [알고리즘 개념정리] 3. 동적계획법(DP)

 

 

 

풀이

두 문자열을 각각 s1, s2라고 하자.

dp[i][j] 에는
s1의 i까지, s2의 j까지 문자들의 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

s1[i] == s2[j] 일때는 dp[i-1][j-1] +1 으로 채우고
s1[i] != s2[j] 일때는 max(dp[i][j-1], dp[i-1][j]로 채우면 된다.

 

참고로 LCS의 길이 뿐만아니라 문자열까지 출력하고싶다면
trace함수를 이용해 위의 표를 거슬러 올라가면 된다.

현재 칸의 값이 바로 왼쪽과 위쪽값보다 더 크다면
s1[i] == s2[j]라서 dp[i-1][j-1] +1 으로 채워진 상황이므로
s1[i] 또는 s2[j]을 answer벡터에 담아놓고 역순으로 출력해주면 된다.

 

 

시간 복잡도

dp 테이블 하나를 채우는 데 O(1)이 걸리므로
총 시간 복잡도는 O(NM)이다.

 

소스코드

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;
typedef long long ll;

int dp[1001][1001]; //s1의 i번째, s2의 j번째 문자까지로 이루어진 문자열들의 LCS길이
char s1[1001],s2[1001];


int foo(int i, int j){
    if(i==-1||j==-1) return 0; // 기저조건
    if(dp[i][j]!=-1) return dp[i][j];
    if(s1[i]==s2[j]) return dp[i][j]=foo(i-1,j-1)+1;
    return dp[i][j]=max(foo(i-1, j), foo(i, j-1));
}

vector<char> answer;
void trace(int i, int j){
    if(i==-1||j==-1) return;
    if(foo(i,j)==foo(i-1,j)) trace(i-1,j);
    else if(foo(i,j)==foo(i,j-1)) trace(i,j-1);
    else if(foo(i,j)==foo(i-1,j-1)+1){
        answer.push_back(s1[i]);
        trace(i-1,j-1);
    }
}

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

    //dp초기화
    for(int i=0; i<1001; i++){
        for(int j=0; j<1001; j++)
            dp[i][j]=-1;
    }
    //문자열입력
    cin>>s1>>s2;

    //LCS길이출력
    cout<<foo(strlen(s1)-1, strlen(s2)-1)<<'\n';

    /*LCS추적, 출력
    trace(strlen(s1)-1, strlen(s2)-1);

    for(int i=answer.size()-1; i>=0; i--)
        cout<<answer[i];
    */
    return 0;
}