[백준 9251] LCS (C++) - 45

문제

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

9251번: LCS

생각

문자열에 많이 약하다는 생각으로 넘겼던 문제이다.

그러나 문자열이 아니라고 생각해도 차이가 없다. (선입견)

LCS 알고리즘을 참고했다.

이 문제는 최대 수열의 길이만 구하면 되는 문제이지만 언제든지 최대 수열을 구하라는 문제가 있을 수 있다.

[알고리즘] 그림으로 알아보는 LCS 알고리즘 - Longest Common Substring와 Longest Common Subsequence

문자열을 받고나서 int 형으로 바꾸려고 안간힘을 썻지만 그럴 필요가 없는 문제이다.

2차원 dp를 한칸 늘리면 해결이 된다.

코드

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

string str1, str2;
int dp[1002][1002];

int main() {
    cin >> str1 >> str2;
    for(int i = 0; i < 1000; i++) {
        dp[i][0] = 0;
        dp[0][i] = 0;
    }
    for(int i = 0; i < str1.size(); i++) {
        for(int j = 0; j < str2.size(); j++) {
            if(str1[i] == str2[j]) dp[i+1][j+1] = dp[i][j] + 1;

            else dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j]);
        }
    }

    cout << dp[str1.size()][str2.size()];
}