[BOJ/c++] 9251 - LCS

링크

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

9251번: LCS

풀이

작년에 dp 공부를 처음하면서 풀지 못했다가 다시 도전해서 푼 문제이다. 최장 공통 부분 수열, 최장 공통 부분 문자열이 다른 것으로 알고 있는데 다음에는 예전에 심심해서 찾아보다가 발견한 최장 공통 부분 문자열 문제를 찾아서 풀어 볼 생각이다.

2차원 dp를 차례대로 채워가면서 s1[i] == s2[i]이면 d[i - 1][j - 1] + 1을 하고 그것이 아니라면 d[i - 1][j]와 d[i][j - 1]의 최대값을 채워 가면된다. 표를 그려서 생각을 하면 더 쉽게 되는 것 같다.

 

코드

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

int d[1001][1001];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string a, b;
    cin >> a >> b;
    for (int i = 1; i <= a.size(); i++) {
        for (int j = 1; j <= b.size(); j++) {
            if (a[i - 1] == b[j - 1]) {
                d[i][j] = d[i - 1][j - 1] + 1;
            } else {
                d[i][j] = max(d[i][j - 1], d[i - 1][j]);
            }
        }
    }
    cout << d[a.size()][b.size()];
    return 0;
}