LCS 백준 - 9251번

LCS문제 입니다. 저는 처음 봤는데, 구글링을 해본 결과, 유명한 문제 유형이더군요. 이 문제도 전에 풀었던 Knapsack문제와 매우 유사하게 풀었습니다. 역시 dp를 사용했습니다.

Dp문제는 너무 어려운 것 같습니다. 보고나면, 쉬운데 발상 자체는 떠올리기가 힘듭니다.

이 문제를 풀기위해서는 한글자씩 비교하면서, 맞으면 갯수+1를 해야 합니다. 하지만, 단순히 모든걸 비교하면, 시간초과가 발생합니다. 결국에는 어떤 방식으로 비교하는 문제가 되는 겁니다. 

 

이 문제는 BFS같은 느낌으로 풀었습니다. 둘이 비교해서 같으면 +1, 다르면 첫번째 문자열만 다음 문자로 넘긴것과 두번째 문자열만 다음 문자로 넘겼을 경우를 비교하여, 둘중 최댓값을 출력하는 겁니다. 

 

출처는 위키백과 https://ko.wikipedia.org/wiki/%EC%B5%9C%EC%9E%A5_%EA%B3%B5%ED%86%B5_%EB%B6%80%EB%B6%84_%EC%88%98%EC%97%B4

#import<bits/stdc++.h>
using namespace std;

void solve(){
	string str1;
	string str2;
    cin>>str1>>str2;
    vector<vector<int>> v(str1.size()+1,vector<int>(str2.size()+1,0));
    for(int i =1;i<=str1.size();i++){
        for(int j =1;j<=str2.size();j++){
            if(str1[i-1] == str2[j-1]){
                v[i][j] = v[i-1][j-1]+1;
            }
            else{
                v[i][j] = max(v[i][j-1],v[i-1][j]);
            }
        }
    }
    cout<<v[str1.size()][str2.size()];
}
int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	solve();
    return 0;
}

이를 코드로 짜면 위와 같이 됩니다. 이차원 배열안에 들어가는 숫자는 각 문자열들의 해당번째의 문자를 비교하는 경우가 됩니다.

 

www.acmicpc.net/problem/9251