[백준 / C++] 9251 LCS - 다이나믹 프로그래밍 (1)

백준 9251번 LSC 문제  

 

문제

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

예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.

입력

첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다.

출력

첫째 줄에 입력으로 주어진 두 문자열의 LCS의 길이를 출력한다.

예제 입력 1 

ACAYKP
CAPCAK

예제 출력 1 

4

 

---

 

LCS 문제 풀이

 

이 문제를 처음 봤을 때, LCS. 즉, 최장 공통 부분수열(Longest Common Subsequence)을 말하는 것이기 때문에 주어진 예제에 어떻게 해야 최장 문자열을 판단할 수 있을 지 고민했다.

 

첫번째로, 시행한 방법은 '재귀'였다. ( 주어진 시간제한을 봤을 때 하지 말았어야했다...) 문제는 잘풀렸지만, 당연히 0.1초라는 시간제한 때문에 실패!

 

두번째 방법은, 문제에 규칙이 존재하고 짧은 시간이다? DP (다이나믹 프로그래밍)을 떠올렸다. 그렇다면 이 문제는 어떤 규칙이 존재할까? 예제 입력 1을 가지고 규칙을 찾아보았다. 

 

 

주어진 "ACAYKP" 에 "CAPCAK"의 각 알파벳을 비교하면서 최댓값을 확인하는 식으로 진행했다.

 

먼저, C를 가지고 "ACAYKP"를 확인한다고 했을 때, 0 1 1 1 1 1 1이다.

 

이 때 규칙은 아래와 같이 2가지 경우이다. 

 

같은 경우

if(str1[i] == str2[j]) dp[i][j] = dp[i-1][j-1] +1

 

다른 경우

dp[i][j] = max(dp[i-1][j], dp[i][j-1])

 

이렇게 2가지 경우로 나눠서 문제를 풀면 된다. 

---

LCS 최종 코드

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

int dp[1001][1001];

int main() {
    cin.tie(0);
    ios::sync_with_stdio(0);

    string str1, str2;
    cin >> str1 >> str2;

    int len1 = str1.size();
    int len2 = str2.size();

    for (int i = 1; i <= len1; i++) {
        for (int j = 1; j <= len2; 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[len1][len2] << "\n";
    return 0;
}