[백준] 9251 LCS c++

 

문제 링크 https://www.acmicpc.net/problem/9251

KEY

LCS문제는 다음과 같이 행열로 두 문자열을 나열한 다음, 이중 for문을 활용해서 풀이한다. 

아래 표를 만들어 내는 것이 핵심이고, 규칙성은 다음과 같다.

• 두 문자가 같은 경우 : 대각선 이전의 값에 1을 더한다.
• 두 문자가 다를 경우 : 자신의 왼쪽과 위쪽 중 최댓값을 취한다. 

Reference: https://comyoung.tistory.com/58

 

Code

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
string str1;
string str2;
int dp[1001][1001];
int main()
{
    cin >> str1 >> str2;
 
    for (int i = 1; i <= str1.size(); i++) {
        for (int j = 1; j <= str2.size(); j++) {
            if (str1[i-1] == str2[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[str1.size()][str2.size()];
 
}