[백준] 9251번 LSC (C)

문제 주소

백준 9251번 LSC

9251번: LCS

알고리즘

DP

힌트

첫번째 문자열의 i번 문자까지의 문자열과 두번째 문자열의 j번 문자까지의 문자열의 LCS의 길이를 구한다.

문제풀이

dp[i][j]에 문자열 a의 i번 문자까지의 문자열과 문자열 b의 j번 문자까지의 문자열의 LCS의 길이를 저장한다.
가장 끝의 문자만 비교하는 식으로 길이를 구해나갈 수 있다.

1. 끝 문자가 같을 경우 dp[i][j] = dp[i-1][j-1]+1
2. 끝 문자가 다를 경우 dp[i][j]는 dp[i][j-1]과 dp[i-1][j]중 더 큰 값이 된다.

#include<iostream>
#include<string>
using namespace std;
int dp[1001][1001];
int main(){
    string a,b;
    cin>>a;
    cin>>b;    
    int n=a.length(), m=b.length();

    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;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[n][m];

}

 

[백준] 9251번 LSC (C)