백준 9251번 - LCS (Longest Common Subsequence)

 

 

 

* 문제 링크

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

9251번: LCS

 

 

 

 

문제 내용 요약

 

문자열이 2개 주어지면 (최대 길이 1000자),

 

공통된 부분 수열 중 가장 긴 거 길이를 출력해라.

 

(Longest Common Subsequence = 최장 공통 부분 수열)

 

 

 

 

 

접근법

 

매우 유명한 다이나믹 프로그래밍 문제 2 정도로 보면 된다.

 

항상 그렇듯이, 무엇을 어떻게 메모할지를 정하는 것이 중요하다.

 

 

 

첫번째 힌트로, 2차원 배열로 메모할 공간을 만들건데

 

m[x][y] 를 1번 문자열 x번째까지, 2번 문자열 y번째까지로 한정했을 때의 LCS 값으로 두고 해보자.

 

 

 

점화식을 짜볼 수 있겠는가?

 

어쨌든 이제 점화식을 세우자.

 

 

1번 문자열 x번째 문자, 2번 문자열 y번째 문자가 같을 경우에는 

 

m[x][y] 는 m[x-1][y-1] 값에 1을 더한 값이 될 것이다. 그리고, m[i][j] 값의 특성상,

 

그것보다 큰 값은 존재하지 않는다.

 

 

다른 경우에는 어떻게 되는가?

 

x 또는 y 전 꺼를 비교해야되지 않겠는가?

 

어떻게 비교하면 되는가?

 

1번의 x번째, 2번의 y-1번째를 비교하고, 1번의 x-1번째, 2번의 y번째를 비교하면 된다.

 

그리고 그 중에 더 큰 것을 써먹으면 된다.

 

 

이제 정리를 해보자.

 

식으로 나타내었다.

 

이제 구현을 해주면 마무리된다.

 

메모이제이션도 까먹지 말고.

 

 

 

 

 

 

내 코드

#include <iostream>
#include <algorithm>
using namespace std;

int mem[1005][1005];
string x,y;

int f(int a,int b) {
    if(a==-1||b==-1) return 1;
    if(mem[a][b]!=0) return mem[a][b];
    if(x.at(a)==y.at(b)) return mem[a][b]=f(a-1,b-1)+1;
    return mem[a][b]=max(f(a-1,b),f(a,b-1));
}

int main() {
    cin>>x>>y;
    cout<<f(x.length()-1,y.length()-1)-1;
}