[c++] 백준 9251 LCS

문제 풀이

[c++] 백준 9251 LCS

미분당한 적분상수 2023. 3. 8. 13:36

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

9251번: LCS

LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.

www.acmicpc.net

LCS는 풀어본적이 없었던 문제였기 때문에, 다른 사람의 답을 참고했다.

다른 비슷한 유형의 문제를 풀어볼 예정이다.

#include<bits/stdc++.h>
using namespace std;
int dp[1010][1010];
vector<char> a,b;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    //입력받기
    string a,b; cin>>a>>b;
    /*
    점화식 돌리기
        ex) APPLE, PENCIL
        APPLE과 P
        APPLE과 PE
        APPLE과 PEN
        .
        .
        APPLE과 PENCIL
        의 LCS를 구하면서 dp테이블을 채우는 방식이다.
        이중 반복문을 돌면서 모든 문자를 서로 비교하는데,
        두 문자가 서로 같을때:
            dp[i][j] = dp[i-1][j-1]+1;
        두 문자가 서로 다를때:
            dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
    */
    for(int i=1; i<=a.size(); i++){
        for(int j=1; j<=b.size(); j++){
            if(a[i-1] == b[j-1])
                dp[i][j] = dp[i-1][j-1]+1;
            else
                dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
        }
    }
    cout << dp[a.size()][b.size()];
    return 0;
}