[C++] 백준 9251 LCS

9251 LCS

9251번: LCS

C++

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

typedef pair<int, int> pi;
typedef long long ll;

string s1, s2;
int DP[1003][1003];

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

    cin >> s1 >> s2;
    s1.insert(s1.begin(), 0);
    s2.insert(s2.begin(), 0);

    for(int i=1; s1[i]; i++){
        for(int j=1; s2[j]; j++){
            DP[i][j] = max(max(DP[i][j-1], DP[i-1][j]), DP[i-1][j-1] + (s1[i]==s2[j]));
        }
    }
    cout << DP[s1.length()-1][s2.length()-1] << '\n';

    return 0;
}

 

DP[i][j]에 s1의 i번째, s2의 j번째 문자까지 탐색해보았을 때 나오는 최장 공통 부분 수열의 길이를 저장하는 방식으로 풀이한다.

 

i-1, j-1 인덱스에 접근하기 위해서 (오류방지용) 0을 각 배열 처음에 추가해준다.

DP[i][j]에는 DP[i][j-1], DP[i-1][j], DP[i-1][j-1] + (s1의 i번째 문자와 s2의 j번째 문자가 같을 경우 1, 아닐 경우 0)

이렇게 세 값 중 최대 값을 넣어주면 된다.