[C++][백준 9251] LCS

[문제]

9251번: LCS (acmicpc.net)

9251번: LCS

---

[문제 풀이]

문제를 풀기 전에 문제의 제목인 LCS 알고리즘에 대해서 배워보도록 하자.

두개의 스트링을 이용해서 기본값이 0인 2차원 배열을 만들어보자.

	A	C	A	Y	K	P
C	0	0	0	0	0	0
A	0	0	0	0	0	0
P	0	0	0	0	0	0
C	0	0	0	0	0	0
A	0	0	0	0	0	0
K	0	0	0	0	0	0

해당 배열을 이용해서 우리들은 두개의 string이 겹치는 최대 길이를 알아보자.

이제 해당 배열에서 일치한다면 숫자를 1씩 더해주자.

	A	C	A	Y	K	P
C	0	1	0	0	0	0
A	1	0	1	0	0	0
P	0	0	0	0	0	1
C	0	1	0	0	0	0
A	1	0	1	0	0	0
K	0	0	0	0	1	0

단순히 1씩 더해서는 만일 같은 문자가 나왔을때 숫자가 오류가 생길 가능성이 있다는 것을 알게 되었다. 그러므로 살짝의 규칙을 더해주기로 했다.

 

	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	2	2	4	4

눈썰미가 좋다면 눈치 챘을 것이다. 숫자가 겹치는 부분은 대각선 윗쪽에서 1을 더해주고 아닐 경우에는 위나 좌측의 숫자를 유지시켜 주는 방식이다.

 

해당 방식을 사용하면 P가 겹쳐서 생기는 3과 같은 문자열이 그 전의 1과 2를 어디서 받아서 생기는지 마지막의 K가 그 전의 어디서 겹쳐서 1, 2, 3을 겪었는지 바로 눈에 보인다.

 

해당 방식을 코드로 짜보면

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;
        }
        else{
            if(dp[i-1][j] >= dp[i][j-1]){
                dp[i][j] = dp[i-1][j];
            }
            else{
                dp[i][j] = dp[i][j-1];
            }
        }
    }
}

이 된다.

이제 해당 함수를 이용해서 문제를 풀어보자.

---

[코드]

#include<iostream>
#include<vector>
#include<string>
#define endl "\n"
using namespace std;

void LCS(string s1,string s2){

    vector<vector<int> > dp(s1.size() + 1,vector<int>(s2.size() + 1));

    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;
            }
            else{
                if(dp[i-1][j] >= dp[i][j-1]){
                    dp[i][j] = dp[i-1][j];
                }
                else{
                    dp[i][j] = dp[i][j-1];
                }
            }
        }
    }

    cout<<dp[s1.size()][s2.size()]<<endl;
    
    return;
}

int main(){
    string lcs_first;
    string lcs_last;
    cin>>lcs_first>>lcs_last;
    LCS(lcs_first,lcs_last);
    return 0;
}